December 7

Recursion

What happens when a function calls itself? Why would you do that? Does is run forever? This week, we’ll talk about recursion.

mirror Credit: blog.stevemould.com

Recursion means that something refers to itself. Usually, recursion views a problem as consisting of sub-problems that are in some sense identical to the problem itself, so the sub-problem can be solved in the same manner.

That’s pretty abstract, so let’s look at a simple example. Suppose I want to print the integers decreasing from some starting number and ending with zero. I can write a function printDecreasing(n) so that, say, printDecreasing(5) prints “5 4 3 2 1 0”.

Now, you know how to write a for loop to do this, but just to be different, let’s think about the problem differently. To print “5 4 3 2 1 0” I can just print “5” then call printDecreasing(4) to print the rest (“4 3 2 1 0”). This is a recursive view of the solution: To solve the problem for N, I print N, then solve the problem for N-1 to print the rest of the sequence.

There are a few loose ends here, especially what happens if N = 0, but we’ll come back to that.

Recursive Problems

If I can solve problems with for loops, why would I need recursion?

Recursive Drawings

Recursion is sometimes a “natural” solution. Here’s an image that would be hard to imagine without recursion:

burg-fig-5Credit: http://idmaa.org

Here’s an interesting recursive program to draw sprial-like forms.

Recursive Data Structures

You may have already used recursion in data structures. In JavaScript, you can have objects with properties. The value of a property can be another object. That object can have properties that are still more objects. This is also an example of recursion.

When you have recursive data structures, it is natural to write recursive programs. For example, if you wanted to convert your recursive object structure to a string, the “natural” algorithm is: To convert an object to a string, start with the empty string and append the string representation of each property and its value. If the value of a property is an object, use this algorithm recursively to compute its string representation.

Local Variables and the Call Stack

To understand recursion more fully, it helps to know what happens to parameters and local variables. Let’s start with non-recursive functions:

function f(x) {
    return x + 1;
}
 
function g(y) {
    return f(y + 1) * 2;
}
 
print(g(3));

When the last line calls g(3), JavaScript creates a stack frame for an instance of g. Inside g the stack looks like this:

g: y = 3

Then g calls f(4). A new stack frame is created for f and the whole stack looks like:

f: x = 4
g: y = 3

Then f computes and returns x + 1 = 4 + 1 = 5. The return statement pops the stack, destroying the local variable x and any other information used by this call to f, leaving:

g: y = 3

Finally, g computes 5 * 2 = 10, and the return statement in g returns 10 to the original caller, the print statement. The stack frame for g is popped, leaving the stack empty.

A similar process takes place with recursion, except that the stack can have multiple frames for the same function. Each frame on the stack holds a copy or instance of each parameter and local variable. This is necessary because each recursive call to a function must be allocated a set of parameters and local variables that are independent of previous calls to the same function. Here is a nice animation from Mark Kahn illustrating a recursive computation of factorial. Recall that the factorial of a number N is N * (N-1) * (N-2) * … * 1. E.g. 3 factorial (written as 3!) is: 3! = 3 * 2 * 1 = 6. The recursive view is that 1! = 1, and N! = N * (N-1)!. Study this animation carefully. It calculates 8!.

stack

Creating Recursive Algorithms

There’s a method for creating recursive algorithms. First, to avoid infinite recursion, every recursive algorithm has to “bottom out” somewhere. This is always done with a conditional that detects the special case for which we know a solution. E.g. in factorial, 1! = 1, case closed, no sub-problem or recursive call. Sometimes in drawings, we have different levels and we just define level 0 to be nothing, no drawing, return immediately. The case where we know the solution immediately is called the base case.

Next, there should be some way to decompose a problem into a smaller instance of itself. E.g. in factorial, to compute N!, we can use the solution to (N-1)!. If we have a multilevel drawing, sometimes for each level N, we draw one or more images recursively at level N-1.

Finally, we put everything together with a conditional and recursive call. The solution often has a form similar to the following template:

function recursiveSolution(x) {
    if (x is the base case) {
        return the solution for x;
    } else {
        var y = a subproblem based on x
        var subsoln = recursiveSolution(y)
        return the solution constructed from x, y, and subsoln
    }
}

Example

For our first example, printing decreasing integers, the base case is either 0 (solution: print “0”) or -1 (solution: do nothing). Let’s choose -1 as the base case. The way to decompose the problem is: printDecreasing(n - 1). We put these together as follows:

function printDecreasing(n) {
    if (n < = -1) {
        return false;
    } else {
        print(n);
        printDecreasing(n - 1);
    }
}

Notice that this solution is not exactly like our generic template above because we have to make the recursive call after printing n. Notice also that we can print the numbers in increasing order if we simply reverse the order of statements in the else clause!

To develop skills writing recursive programs, here are some nice introductory exercises and solutions.