A definition is recursive if it refers to itself. A recursive function calls itself. A recursive structure contains components that are the same as the structure being defined.

It can seem mind bending at first. But recursion is the Popeye's spinach of procedural abstraction — learn to use it, and you become a powerful problem solver.

There is no magic. When you call a function, the programming language implementation doesn't care whether that function is one you're executing or another one. The exact same thing happens no matter what (find the function, evaluate arguments, make stack frame, etc.).

Recursion comes about as a special case of Big Idea #3: Divide-Conquer-Glue. You take a problem and divide it up into smaller problems, one or more of which looks like a smaller version of the original problem. Picture nested matryoshka dolls.

When you write or try to write or understand a recursive function you must:

• Identify one or more base cases where the answer can be computed immediately. These cases are are where the repetition stops.
• Identify one or more recursive cases where you can break a problem into pieces that look like smaller versions of the original problem. These smaller problems are solved using recursive calls and then are glued together. Some aspect of the problem must get smaller with each recursive call.

Example Recursive Functions

Consdider the problem of automating the NASA's launch count down sequence (count_down.cpp).

void count_down(int n)
{
        if (n == 0)
                printf("Blastoff!\n");
        else {
                printf("%d\n", n);
                count_down(n - 1);
        }
}
      

In this case, we broke the problem of counting down from some n into two cases. If n is 0, we know what to do: Blastoff! If not, then we can call out n, but we still have the problem of counting down from n - 1. That subproblem looks like the original problem, but slightly smaller.

A classic example: compute the factorial of a number.

The factorial of the non-negative integer n is:

• 1, if n = 0
• 1 × 2 × … n, otherwise

int factorial(int n)
{
        if (n == 0)
                return 1;
        else
                return n * factorial(n - 1);
}
      

Two ways to think about functions

1. the mechanical view of a function
   1. locate the appropriate function object
   2. evaluate the arguments expressions left-to-right
   3. create an activation record (stack frame) for the function
   4. assign the values of the arguments to the parameters
   5. execute the body of the function
   6. save the return value (if any) and recycle the activation record
   7. replace the original function call with the return value
   8. pick up where you left off
2. abstract view of a function (like mathematical induction):
   • Define behavior/value for simplest/smallest cases.
   • Assume that the function works according to its interface (inputs, preconditions, side-effects, postconditions, return value) for smaller versions of the problem and figure out how to make a solution for the slightly larger version.
   • Don't think about how it works
   • Don't follow the flow of execution

To write a recursive solution to a problem, you will need to shift back and forth betwen different levels of abstraction: your code will be both an implementation of the solution, and a client of the solution.

1. Start by thinking through examples. Look at particular inputs/configurations and write down what the appropriate output or ending configurations should be. Don't forget to consider degenerate cases (values including 0, empty strings/lists/...). Pictures are good.
2. Identify one or more base cases (students usually start by having too many base cases, but see below). These are circumstances under which no recursive steps need be taken. Identify solutions for each base case.
3. In the general, or recursive cases, we will need to divide the problem into pieces. One or more pieces will look like the original problem.

   When figuring out how to decompose the general case problems, you'll have to figure out what unit of work to do at a time, ie, how much work each invocation of the function will perform, and how much will be left for the recursive invocations. This can be very tricky, and inexperience with abstractions makes beginning programmers think too far ahead (both in the general and base cases). Typically, you'll want to take a small bite out of the problem in each invocation. For example, in a linked list application, you'll typically deal with only one list element at a time, using recursion for the entire rest of the list. Following the structure of data is often a good way to start.

4. Shift to client mode and assume that the function works on the recursive subproblem. This is often called the “recursive leap of faith.” Make the recursive calls, and then assume the smaller problems have been solved.
5. Figure out what to do with the bit of the problem you're not passing on to recursive calls.
6. Glue the results from the previous two steps together.

Examples

There are examples in recursion_examples.cpp.

In that file, you'll find an iterative (looping) factorial called factIter() as well as the classic recursive formulation shown above (in factRec()). You'll also see a tail recursive formulation (see below) in factTail() and factTailHelper().

Another classic example involves the Fibonacci sequence. The Fibonacci numbers form a sequence that arises often in nature, because it represents a kind of a growth pattern. The name comes from 13^th century math texbook by Leonardo Pisano (aka, Fibonacci). In that text book, there is a problem that deals with rabbits: immortal rabbits that reproduce like clockwork. We count them in breeding pairs. A breeding pair of rabbits takes a month to mature, so they don't produce babies in their first month. But after that, they produce a new breeding pair every month, forever.

You start with an empty field, so at time 0, there are 0 breeding pairs of rabbits. Then you put in a breeding pair, so at month 1, there is 1 pair. It takes the pair a month to mature, so at month 2, there is still 1 breeding pair. The first pair then produces a second breeding pair, so in month 3 you have 2 breeding pairs. In month 4, the first pair produces another pair, and their first offspring mature, making a total of 3 pairs. In month 5 the first and second pairs produce offspring and the third pair mature, making 5 breeding pairs.

Do you see the pattern? In any month, all the rabbit pairs that are mature produce a new pair. How can we compute the number of pairs of rabbits in any given month? Well, in any month, the number of pairs is the number of pairs you had the previous month plus the number of pairs that produced offspring. Since it takes a month to mature, the number of pairs that can produce offspring are the number of pairs more than one month old, which is the number of pairs you had two months ago.

The Fibonacci number for n is therefore:

• 0 if n = 0
• 1 if n = 1
• and the sum of the Fibonacci numbers for (n - 1) and (n - 2) for n > 1

int fibRec(int n)
{
        if (n == 0)
                return 0;
        else if (n == 1)
                return 1;
        else
                return fibRec(n - 1) + fibRec(n - 2);
}
          

In the example file, you'll find the above function as well as an iterative (loop-based) version called fibIter().

Try to write a function, pow(), that takes a base and exponent and returns base^exponent. The example file contains a solution, but try it on your own first.

Finally, consider the Towers of Hanoi problem. This puzzle is a common children's puzzle, that looks like this:

There's a story of monastery in which there are 3 poles in a yard with 64 stone disks. The disks start on one pole, largest at the bottom. The monks are moving the stack of disks from the original pole to a destination pole according to the following rules:

• Only one disk can be moved at a time
• A larger disk must never be placed atop a smaller disk

When they complete the move, the universe comes to an end. Are we safe?

Can you write a program that solves the puzzle? Start with 1, 2, 3, and 4 disks. Can you see a pattern? You can try to solve this iteratively. It can be done, but it's rather complicated. However, there is an extremely simple, elegant, and obviously correct recursive solution.

Exercise:
Write a recursive solution the problem: Write a function

void hanoi(int num_disks, string source, 
           string destination, string spare);
        

that prints out instructions for solving the puzzle. You may use the following helper function:

void move(int disk, string from, string to)
{
        cout << "Move disk " << disk
             << " from "     << from
             << " to "       << to
             << endl;
}
        

We'll number the disks from the top, i.e., the top-most disk is disk number 1, the bottom one is num_disks. (Using this numbering scheme means you don't have to have a list of disks: you can just pass the number of lowest disk in a stack, which is also the number of disks in the stack.)

hanoi(3, "a", "b", "c"); should print:

    Move disk 1 from a to b
    Move disk 2 from a to c
    Move disk 1 from b to c
    Move disk 3 from a to b
    Move disk 1 from c to a
    Move disk 2 from c to b
    Move disk 1 from a to b
        

Really try to solve it and write the program. I'll show you my solution in class.

Tail Recursion

If function f calls function g, then the call to g is said to be a tail call if f immediately returns the result of g without any further processing, or, if g doesn't return a value (is void), f returns immediately after calling g. Throwing away a return value counts as additional processing.

A function is tail recursive if all of its recursive calls are tail calls.

The count_down() function above is tail recursive. It doesn't do anything but return after the recursive call.

The factorial() function above is not tail recursive, because it multiplies the result of the recursive call by n.

We can write a tail recursive solution to factorial. We'll wind up using a helper function:

int factorial_helper(int n, int answer_so_far)
{
        if (n == 0)
                return answer_so_far;
        else
                return factorial_helper(n - 1, 
                                        n * answer_so_far);
}

int factorial(int n)
{
        return factorial_helper(n, 1);
}
        

Why do we care? Because tail recursive solutions have a very straightforward relationship to iterative solutions:

int factorial(int n)
{
        int answer_so_far = 1;

        for ( ; n > 0; --n) 
                answer_so_far *= n;

        return answer_so_far;
}
        

This is very cool. As in this example, a tail recursive solution to a problem often involves adding extra parameters that carry along state that would have been accumulated on the way back up the call chain. The initial value(s) of such state parameters are usually related to the result(s) in the base case(s).

The relationship is so straightforward, that some laguages/compilers will automatically convert a tail recursive function to an iteration so that the function doesn't use any stack space beyond the initial activation record. Never, C or C++ or Java. But Scheme, SML, and other languages do this.