Recursion is when a function calls itself. Some programming languages (particularly functional programming languages like Scheme, ML, or Haskell) use recursion as a basic tool for implementing algorithms that in other languages would typically be expressed using iteration (loops). Procedural languages like C tend to emphasize iteration over recursion, but can support recursion as well.

1. Example of recursion in C

Here are a bunch of routines that print the numbers from 0 to 9:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 
   5 /* all of these routines print numbers i where start <= i < stop */
   6 
   7 void
   8 printRangeIterative(int start, int stop)
   9 {
  10     int i;
  11 
  12     for(i = start; i < stop; i++) {
  13         printf("%d\n", i);
  14     }
  15 }
  16 
  17 void
  18 printRangeRecursive(int start, int stop)
  19 {
  20     if(start < stop) {
  21         printf("%d\n", start);
  22         printRangeRecursive(start+1, stop);
  23     }
  24 }
  25 
  26 void
  27 printRangeRecursiveReversed(int start, int stop)
  28 {
  29     if(start < stop) {
  30         printRangeRecursiveReversed(start+1, stop);
  31         printf("%d\n", start);
  32     }
  33 }
  34 
  35 void
  36 printRangeRecursiveSplit(int start, int stop)
  37 {
  38     int mid;
  39 
  40     if(start < stop) {
  41         mid = (start + stop) / 2;
  42 
  43         printRangeRecursiveSplit(start, mid);
  44         printf("%d\n", mid);
  45         printRangeRecursiveSplit(mid+1, stop);
  46     }
  47 }
  48 
  49 #define Noisy(x) (puts(#x), x)
  50 
  51 int
  52 main(int argc, char **argv)
  53 {
  54 
  55     if(argc != 1) {
  56         fprintf(stderr, "Usage: %s\n", argv[0]);
  57         return 1;
  58     }
  59 
  60     Noisy(printRangeIterative(0, 10));
  61     Noisy(printRangeRecursive(0, 10));
  62     Noisy(printRangeRecursiveReversed(0, 10));
  63     Noisy(printRangeRecursiveSplit(0, 10));
  64 
  65     return 0;
  66 }

And here is the output:

printRangeIterative(0, 10)
0
1
2
3
4
5
6
7
8
9
printRangeRecursive(0, 10)
0
1
2
3
4
5
6
7
8
9
printRangeRecursiveReversed(0, 10)
9
8
7
6
5
4
3
2
1
0
printRangeRecursiveSplit(0, 10)
0
1
2
3
4
5
6
7
8
9

The first function printRangeIterative is simple and direct: it's what we've been doing to get loops forever. The others are a bit more mysterious.

The function printRangeRecursive is an example of solving a problem using the DivideAndConquer method. If we don't know how to print a range of numbers 0 through 9, maybe we can start by solving a simpler problem of printing the first number 0. Having done that, we have a new, smaller problem: print the numbers 1 through 9. But then we notice we already have a function printRangeRecursive that will do that for us. So we'll call it.

If you aren't used to this, it has the feeling of trying to make yourself fly by pulling very hard on your shoelaces.¹ But in fact the computer will happily generate the eleven nested instances of printRangeRecursive to make this happen. When we hit the bottom, the call stack will look something like this:

printRangeRecursive(0, 10)
 printRangeRecursive(1, 10)
  printRangeRecursive(2, 10)
   printRangeRecursive(3, 10)
    printRangeRecursive(4, 10)
     printRangeRecursive(5, 10)
      printRangeRecursive(6, 10)
       printRangeRecursive(7, 10)
        printRangeRecursive(8, 10)
         printRangeRecursive(9, 10)
          printRangeRecursive(10, 10)

This works because each call to printRangeRecursive gets its own parameters and its own variables separate from the others, even the ones that are still in progress. So each will print out start and then call another copy in to print start+1 etc. In the last call, we finally fail the test start < stop, so the function exits, then its parent exits, and so on until we unwind all the calls on the stack back to the first one.

In printRangeRecursiveReversed, the calling pattern is exactly the same, but now instead of printing start on the way down, we print start on the way back up, after making the recursive call. This means that in printRangeRecursiveReversed(0, 10), 0 is printed only after the results of printRangeRecursiveReversed(1, 10), which gives us the countdown effect.

So far these procedures all behave very much like ordinary loops, with increasing values on the stack standing in for the loop variable. More exciting is printRangeRecursiveSplit. This function takes a much more aggressive approach to dividing up the problem: it splits a range [0, 10) as two ranges [0, 5) and [6, 10) separated by a midpoint 5.² We want to print the midpoint in the middle, of course, and we can use printRangeRecursiveSplit recursively to print the two ranges. Following the execution of this procedure is more complicated, with the start of the sequence of calls looking something like this:

printRangeRecursiveSplit(0, 10)
 printRangeRecursiveSplit(0, 5)
  printRangeRecursiveSplit(0, 2)
   printRangeRecursiveSplit(0, 1)
    printRangeRecursiveSplit(0, 0)
    printRangeRecursiveSplit(1, 1)
   printRangeRecursiveSplit(2, 2)
  printRangeRecursiveSplit(3, 5)
   printRangeRecursiveSplit(3, 4)
    printRangeRecursiveSplit(3, 3)
    printRangeRecursiveSplit(4, 4)
   printRangeRecursiveSplit(5, 5)
 printRangeRecursiveSplit(6, 10)
  ... etc.

Here it is not so obvious how one might rewrite this procedure as a loop.

2. Common problems with recursion

Like iteration, recursion is a powerful tool that can cause your program to do much more than expected. While it may seem that errors in recursive functions would be harder to track down than errors in loops, most of the time there are a few basic causes.

2.1. Omitting the base case

Suppose we leave out the if statement in printRangeRecursive:

   1 void
   2 printRangeRecursiveBad(int start, int stop)
   3 {
   4     printf("%d\n", start);
   5     printRangeRecursiveBad(start+1, stop);
   6 }

This will still work, in a sense. When called as printRangeRecursiveBad(0, 10), it will print 0, call itself with printRangeRecursiveBad(1, 10), print 1, 2, 3, etc., but there is nothing to stop it at 10 (or anywhere else). So our output will be a long string of numbers followed by a segmentation fault, when we blow out the stack.

This is the recursive version of an infinite loop: the same thing happens if we forget a loop test and write

   1 void
   2 printRangeIterativeBad(int start, int stop)
   3 {
   4     for(i = 0; ; i++) {
   5         printf("%d\n", i);
   6 }

except that now the program just runs forever, since it never runs out of resources. (This is an example of how iteration is more efficient than recursion, at least in C.)

2.2. Blowing out the stack

Blowing out the stack is what happens when a recursion is too deep. Typically, the operating system puts a hard limit on how big the stack can grow, on the assumption that any program that grows the stack too much has gone insane and needs to be killed before it does more damage. One of the ways this can happen is if we forget the base case as above, but it can also happen if we just try to use a recursive function to do too much. For example, if we call printRangeRecursive(0, 1000000), we will probably get a segmentation fault after the first 100,000 numbers or so.

For this reason, it's best to try to avoid linear recursions like the one in printRangeRecursive, where the depth of the recursion is proportional to the number of things we are doing. Much safer are even splits like printRangeRecursiveSplit, since the depth of the stack will now be only logarithmic in the number of things we are doing. Fortunately, linear recursions are often tail-recursive, where the recursive call is the last thing the recursive function does; in this case, we can use a standard transformation (see below) to convert the tail-recursive function into an iterative function.

2.3. Failure to make progress

Sometimes we end up blowing out the stack because we thought we were recursing on a smaller instance of the problem, but in fact we weren't. Consider this broken version of printRangeRecursiveSplit:

   1 void
   2 printRangeRecursiveSplitBad(int start, int stop)
   3 {
   4     int mid;
   5 
   6     if(start == stop) {
   7         printf("%d\n", start);
   8     } else {
   9         mid = (start + stop) / 2;
  10 
  11         printRangeRecursiveSplitBad(start, mid);
  12         printRangeRecursiveSplitBad(mid, stop);
  13     }
  14 }

This will get stuck on as simple a call as printRangeRecursiveSplitBad(0, 1); it will set mid to 0, and while the recursive call to printRangeRecursiveSplitBad(0, 0) will work just fine, the recursive call to printRangeRecursiveSplitBad(0, 1) will put us back where we started, giving an infinite recursion.

Detecting these errors is usually not too hard (segmentation faults that produce huge piles of stack frames when you type where in gdb are a dead give-away). Figuring out how to make sure that you do in fact always make progress can be trickier.

3. Tail-recursion versus iteration

Tail recursion is when a recursive function calls itself only once, and as the last thing it does. The printRangeRecursive function is an example of a tail-recursive function:

   1 void
   2 printRangeRecursive(int start, int stop)
   3 {
   4     if(start < stop) {
   5         printf("%d\n", start);
   6         printRangeRecursive(start+1, stop);
   7     }
   8 }

The nice thing about tail-recursive functions is that we can always translate them directly into iterative functions. The reason is that when we do the tail call, we are effectively replacing the current copy of the function with a new copy with new arguments. So rather than keeping around the old zombie parent copy—which has no purpose other than to wait for the child to return and then return itself—we can reuse it by assigning new values to its arguments and jumping back to the top of the function.

Done literally, this produces this goto-considered-harmful monstrosity:

   1 void
   2 printRangeRecursiveGoto(int start, int stop)
   3 {
   4     topOfFunction:
   5 
   6     if(start < stop) {
   7         printf("%d\n", start);
   8 
   9         start = start+1;
  10         goto topOfFunction;
  11     }
  12 }

But we can always remove goto statements using less offensive control structures. In this particular case, the pattern of jumping back to just before an if matches up exactly with what we get from a while loop:

   1 void
   2 printRangeRecursiveNoMore(int start, int stop)
   3 {
   4     while(start < stop) {
   5         printf("%d\n", start);
   6 
   7         start = start+1;
   8     }
   9 }

In functional programming languages, this transformation is usually done in the other direction, to unroll loops into recursive functions. Since C doesn't like recursive functions so much (they blow out the stack!), we usually do this transformation got get rid of recursion instead of adding it.

4. An example of useful recursion

So far the examples we have given have not been very useful, or have involved recursion that we can easily replace with iteration. Here is an example of a recursive procedure that cannot be as easily turned into an iterative version.

We are going to implement the Mergesort algorithm on arrays. This is a classic DivideAndConquer sorting algorithm that splits an array into two pieces, sorts each piece (recursively!), then merges the results back together. Here is the code, together with a simple test program.

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 
   5 /* merge sorted arrays a1 and a2, putting result in out */
   6 void
   7 merge(int n1, const int a1[], int n2, const int a2[], int out[])
   8 {
   9     int i1;
  10     int i2;
  11     int iout;
  12 
  13     i1 = i2 = iout = 0;
  14 
  15     while(i1 < n1 || i2 < n2) {
  16         if(i2 >= n2 || (i1 < n1) && (a1[i1] < a2[i2])) {
  17             /* a1[i1] exists and is smaller */
  18             out[iout++] = a1[i1++];
  19         }  else {
  20             /* a1[i1] doesn't exist, or is bigger than a2[i2] */
  21             out[iout++] = a2[i2++];
  22         }
  23     }
  24 }
  25 
  26 /* sort a, putting result in out */
  27 /* we call this mergeSort to avoid conflict with mergesort in libc */
  28 void
  29 mergeSort(int n, const int a[], int out[])
  30 {
  31     int *a1;
  32     int *a2;
  33 
  34     if(n < 2) {
  35         /* 0 or 1 elements is already sorted */
  36         memcpy(out, a, sizeof(int) * n);
  37     } else {
  38         /* sort into temp arrays */
  39         a1 = malloc(sizeof(int) * (n/2));
  40         a2 = malloc(sizeof(int) * (n - n/2));
  41 
  42         mergeSort(n/2, a, a1);
  43         mergeSort(n - n/2, a + n/2, a2);
  44 
  45         /* merge results */
  46         merge(n/2, a1, n - n/2, a2, out);
  47 
  48         /* free the temp arrays */
  49         free(a1);
  50         free(a2);
  51     }
  52 }
  53 
  54 #define N (10)
  55 
  56 int
  57 main(int argc, char **argv)
  58 {
  59     int a[N];
  60     int b[N];
  61     int i;
  62 
  63     for(i = 0; i < N; i++) {
  64         a[i] = N-i-1;
  65     }
  66 
  67     for(i = 0; i < N; i++) {
  68         printf("%d ", a[i]);
  69     }
  70 
  71     putchar('\n');
  72 
  73     mergeSort(N, a, b);
  74 
  75     for(i = 0; i < N; i++) {
  76         printf("%d ", b[i]);
  77     }
  78 
  79     return 0;
  80 }

The cost of this is pretty cheap: O(n log n), since each element of a is processed through merge once for each array it gets put in, and the recursion only goes log n layers deep before we hit 1-element arrays.

CategoryProgrammingNotes