COMP15 Spring 2018
Data Structures
Last updated January 09, 2018 14:40:26 EST

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 :

```void count_down(int n)
{
if (n == 0)
cout << "Blastoff!\n";
else {
cout << "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.

Laney Strange
Last updated January 09, 2018 14:40:26 EST