• Show understanding of recursion

  • Essential features of recursion

  • How recursion is expressed in a programming language

  • Write and trace recursive algorithms

  • When the use of recursion is beneficial

• Show awareness of what a compiler has to do to translate recursive programming code

  • Use of stacks and unwinding

A recursive routine has several parts to it:

• • General case:  The general case is the part of the problem that calls the same routine to solve a subset of the problem

  • Base case:  The base case is the smallest version of the problem that can be easily solved.

The base case is an essential component of the routine, which prevents an infinite loop.  Very often, you also need more than one base case, including trapping any errors that could also cause an infinite loop.  Although in reality, infinite loops would be impossible as the computer would most probably run out of memory.

Another way to look at this is the general case is where the solution is expressed in terms of a smaller version of itself. In other words, here, the problem space is made smaller and smaller. (the smaller problem space is sent to the calling function) base case--the case for which the solution can be stated nonrecursively. The base case is the smallest version of the problem for which we can calculate an answer. With factorials, knowing the factorial of 1 allows us to then unwind.

The rule of thumb for recursion is, "Use recursion, if and only if on each iteration your task splits into two or more similar tasks".  Fibonacci is not a good example of recursion application, while the Towers of Hanoi is a good one.

So most of the good examples of recursion are tree traversal in different disguises.

For example: graph traversal - the requirement that visited node will never be visited again effectively makes graph a tree (a tree is a connected graph without simple cycles).  Divide and conquer algorithms (quick sort, merge sort) - parts after "divide" constitute children nodes, "conquer" constitutes edges from parent node to child nodes.

The following code, written in Java, counts the number of files within a file subsystem.  This type of program would be much more difficult implemented as a non-recursive routine.  Using this example, you can see how the use of recursion allows us to break each successive folder to complete the same task.

public static int countFiles(File f) {

    if (f.isFile()){

        return 1;

    }

    // Count children & recurse into subdirs:

    int count = 0;

    File[] files = f.listFiles();

    for (File fileOrDir : files) {

        count += countFiles(fileOrDir);

    }

    return count;

}

In the majority of major imperative language implementations (i.e. every major implementation of C, C++, Basic, Python, Ruby,Java, and C#) iteration is vastly preferable to recursion.

To see why, walk through the steps that the above languages use to call a function:

• space is carved out on the stack for the function's arguments and local variables

• the function's arguments are copied into this new space

• control jumps to the function

• the function's code runs

• the function's result is copied into a return value

• the stack is rewound to its previous position

• control jumps back to where the function was called

Doing all of these steps takes time, usually a little bit more than it takes to iterate through a loop. However, the real problem is in step #1. When many programs start, they allocate a single chunk of memory for their stack, and when they run out of that memory (often, but not always due to recursion), the program crashes due to a stack overflow.

So in these languages, recursion is slower and it makes you vulnerable to crashing. There are still some reasons why recursion is still useful and necessary, and in general, code written recursively is shorter and a bit more elegant once you know how to read it.

There is a technique that language implementers can use called tail call optimization, which can eliminate some classes of stack overflow. Put succinctly: if a function's return expression is simply the result of a function call, then you don't need to add a new level onto the stack, you can reuse the current one for the function being called. Regrettably, few imperative language implementations have tail-call optimisation built in.