last modified 3/6/01

Recursion

The basic idea behind a recursive function is that you can solve a problem by breaking it into smaller pieces, solving each of those smaller pieces by breaking them up into even smaller pieces, and so on.

The two basic parts of a recursive function:

  1. the base case - without a base case, your recursive function will never terminate. For functions of natural numbers, N=0 is usually the base case.
  2. the recursive part - this part implements the concept that you can 'solve the problem' by solving a smaller problem. If this doesn't make sense to you right away, don't worry about it. Your intuition will improve with practice.

An example recursive function to think about is one that computes the sum of the natural numbers from 0 to N. The important thing to understand here is that the sum of the natural numbers from 0 to N is equal to the sum of natural number from 0 to N-1 plus N. Read that again. Yes, it sounds trivial. But that's what makes recursion so powerful: its elegant simplicity. In writing recursive functions, you need to be able to think about problems like this. Sometimes, using actual numbers can help.

Example: If I tell you that I have a function f() that can compute the sum of numbers from 0 to 100 and then ask you to compute the sum of numbers from 0 to 101 using that function, you could easily write the expression f() + 101 to give me the correct answer.

If you understand that example, you just need to generalize that idea to understand this example function:

int sum(int N)
{
   if (N == 0) return 0;
   return N + sum(N - 1);
}

question: how could you change the function to print the sum of two times each number from 0 to N? answer

Iteration and recursion - any function that can be written recursively can also be written iteratively. For the example function given above, the equivalent iterative function would be:

int f(int N)
{
    int count, sum = 0;
    for (count = 0; count <= N; count++)
        sum = sum + count;
    return sum;
}

(You could also use a while loop...)

Possible pitfall with recursion

Sometimes the straightforward recursive solution is not computationally efficient. The lecture notes show a tree-like illustration for the operation of the Fibonacci numbers function. Drawing trees to trace through recursive functions is an effective method for understanding/debugging recursive functions.

Dynamic programming is offered as a technique which can be used to make recursive functions more efficient. The basic idea of dynamic program is that you use an array (or some other appropriate data structure) to save intermediate results and avoid duplicating computations.

(See sections 5.1 and 5.3 of Sedgewick.)

Implementing recursion

It's important to understand that recursive functions do not execute any differently than normal functions in C. They are still 'called' from another function. Execution stops in the calling function, until the 'called' function returns. When the execution stops, the 'environment' of the calling function must be saved. In simple terms, we need to save the values of local variables so that we'll be able to use them when we return. So, we 'push' the environment of the function onto a stack...and then when we return to the calling function, we pop from the stack to 'restore the environment.'

Parameters are passed into a recursive function in the same way as in a regular function. Copies of the values are used to initialize the variables in the parameter list that will be used in the function.

One way to think about how functions are executed, which may help, is to imagine that the code of the function is actually copied over the function call. Here's an illustration of that idea:

A non-recursive function call: 
int f (int k)
{
   return k + 2;
}
      
void main()
{
    int y; 
    int x = 5;
    y = f(x);
    printf("y is %d\n", y);
}

You can think of the above example as being equivalent to this:

void main()
{
    int y;    
    int x = 5;
    y = x + 2;     // copy the code of f() here, with k replaced by x
    printf("y is %d\n", y);
}

It should be plain to see that both versions are equivalent.

You can trace through a recursive function be repeatedly 'pasting' in its code whenever it calls itself. Example (factorial function):

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

Let's trace through the function with the pasting technique for n=4:

f(4)
{
   if (4 == 0) return 1;   // n is 4 here
   return 4 * f(3)
              {
                 if (3 == 0) return 1;  // we just 'pasted' the code here
                 return 3 * f(2)
                            {
                               if (2 == 0) return 1;  //n is 2 here
                               return 2 * f(1)
                                          {
                                             if (1 == 0) return 1;
                                             return 1 * f(0)
                                                        {
                                                           if (0 == 0) return 1;

Now what? Well, we've finally gotten to the base case. We don't need to 'paste' again, because we don't get to that line. We just return 1 here. (You can see why base cases are so important - without them, we'd never finish 'pasting.') We haven't finished yet, though...

f(0) just finished its execution. There's no mystery about what happens next. Whenever any function finishes (returns), its return value (if any) is returned to the calling function and execution resumes there. Make sure you understand this - it's critical.

So, the value 1 is returned. In the function f(1), we were executing the line "return 1 * f(0)" when f(0) was called. So, we continue: f(1) will return 1 * 1 to its current function: f(2). Then, f(2) will return 2 * f(1), which is 2 * 1. Next, this value, 2, is returned to f(3), so f(3) finishes by executing the line: 3 * f(2). The number returned by f(2) is 2. Thus, 3 * 2 is returned by f(3), and we're done - with the correct result, 3.

An alternative way to think about the execution of a recursive function is with a pushdown stack:

For our example, the stack would have the following sequence of values: (read from left to right)

         
                     f(0)   1
              f(1)   f(1)   f(1)   1*1
       f(2)   f(2)   f(2)   f(2)   f(2)   2*1
f(3)   f(3)   f(3)   f(3)   f(3)   f(3)   f(3)   3*2

 

Questions from Students

  1. I have some problems doing the last question on recursion in the first midterm in the course packet. It's the one that returns f(f(x+5)... Could you help me with that ?
     

main page