Recursion

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.

Example of recursion in C

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

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* all of these routines print numbers i where start <= i < stop */

void
printRangeIterative(int start, int stop)
{
    int i;

    for(i = start; i < stop; i++) {
        printf("%d\n", i);
    }
}

void
printRangeRecursive(int start, int stop)
{
    if(start < stop) {
        printf("%d\n", start);
        printRangeRecursive(start+1, stop);
    }
}

void
printRangeRecursiveReversed(int start, int stop)
{
    if(start < stop) {
        printRangeRecursiveReversed(start+1, stop);
        printf("%d\n", start);
    }
}

void
printRangeRecursiveSplit(int start, int stop)
{
    int mid;

    if(start < stop) {
        mid = (start + stop) / 2;

        printRangeRecursiveSplit(start, mid);
        printf("%d\n", mid);
        printRangeRecursiveSplit(mid+1, stop);
    }
}

#define Noisy(x) (puts(#x), x)

int
main(int argc, char **argv)
{

    if(argc != 1) {
        fprintf(stderr, "Usage: %s\n", argv[0]);
        return 1;
    }

    Noisy(printRangeIterative(0, 10));
    Noisy(printRangeRecursive(0, 10));
    Noisy(printRangeRecursiveReversed(0, 10));
    Noisy(printRangeRecursiveSplit(0, 10));

    return 0;
}

examples/recursion/recursion.c

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 a divide and conquer approach. 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. (The notation [x, y) means all numbers z such that x ≤ z < y.) 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 the computation has the structure of a tree instead of a list, so it is not so obvious how one might rewrite this procedure as a loop.

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.

Omitting the base case

Suppose we leave out the if statement in printRangeRecursive:

void
printRangeRecursiveBad(int start, int stop)
{
    printf("%d\n", start);
    printRangeRecursiveBad(start+1, stop);
}

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

void
printRangeIterativeBad(int start, int stop)
{
    for(i = 0; ; i++) {
        printf("%d\n", i);
    }
}

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.

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 wrong and needs to be stopped 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 to convert the tail-recursive function into an iterative function.

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:

void
printRangeRecursiveSplitBad(int start, int stop)
{
    int mid;

    if(start == stop) {
        printf("%d\n", start);
    } else {
        mid = (start + stop) / 2;

        printRangeRecursiveSplitBad(start, mid);
        printRangeRecursiveSplitBad(mid, stop);
    }
}

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.

Tail-recursion and iteration

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

void
printRangeRecursive(int start, int stop)
{
    if(start < stop) {
        printf("%d\n", start);
        printRangeRecursive(start+1, stop);
    }
}

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:

void
printRangeRecursiveGoto(int start, int stop)
{
    topOfFunction:

    if(start < stop) {
        printf("%d\n", start);

        start = start+1;
        goto topOfFunction;
    }
}

But we can almost always remove goto statements using less dangerous 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:

void
printRangeRecursiveNoMore(int start, int stop)
{
    while(start < stop) {
        printf("%d\n", start);

        start = start+1;
    }
}

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.

Binary search: recursive and iterative versions

Binary search is an algorithm for searching a sorted array for a particular target element, similar to playing Twenty Questions when the answer is a number (hopefully in a range that includes at most 220 numbers). The algorithm starts by picking an value in the middle of the array. If the target is less than this value, we recurse on the bottom half of the array; else we recurse on the top half.

Here is an interface for binary search on an array of ints:

/* returns 1 if target is present in sorted array */
int binarySearch(int target, const int *a, size_t length);

examples/binarySearch/binarySearch.h

Written recursively, we might implement the algorithm like this:

#include <stddef.h>

#include "binarySearch.h"

int
binarySearch(int target, const int *a, size_t length)
{
    size_t index;

    index = length/2;

    if(length == 0) {
        /* nothing left */
        return 0;
    } else if(target == a[index]) {
        /* got it */
        return 1;
    } else if(target < a[index]) {
        /* recurse on bottom half */
        return binarySearch(target, a, index);
    } else {
        /* recurse on top half */
        /* we throw away index+1 elements (including a[index]) */
        return binarySearch(target, a+index+1, length-(index+1));
    }
}

examples/binarySearch/binarySearchRecursive.c

This will work just fine, and indeed it finds the target element (or not) in O(log n) time, because we can only recurse O(log n) times before running out of elements and we only pay O(1) cost per recursive call to binarySearch. But we do have to pay function call overhead for each recursive call, and there is a potential to run into stack overflow if our stack is very constrained.

Fortunately, we don’t do anything with the return value from binarySearch but pass it on up the stack: the function is tail-recursive. This means that we can get rid of the recursion by reusing the stack from from the initial call. The mechanical way to do this is wrap the body of the routine in a for(;;) loop (so that we jump back to the top whenever we hit the bottom), and replace each recursive call with one or more assignments to update any parameters that change in the recursive call. The result looks like this:

#include <stddef.h>

#include "binarySearch.h"

int
binarySearch(int target, const int *a, size_t length)
{
    size_t index;

    /* direct translation of recursive version */
    /* hence the weird organization of the loop */
    for(;;) {
        index = length/2;

        if(length == 0) {
            /* nothing left */
            return 0;
        } else if(target == a[index]) {
            /* got it */
            return 1;
        } else if(target < a[index]) {
            /* recurse on bottom half */
            length = index;
        } else {
            /* recurse on top half */
            /* we throw away index+1 elements (including a[index]) */
            a = a + index + 1;
            length = length - (index + 1);
        }
    }
}

examples/binarySearch/binarySearchIterative.c

Here’s some simple test code to demonstrate that these two implementations in fact do the same thing: Makefile, testBinarySearch.c.

Mergesort: a recursive sorting algorithm

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 turned into an iterative version so easily.

We are going to implement the mergesort algorithm on arrays. This is a classic divide and conquer 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.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* merge sorted arrays a1 and a2, putting result in out */
void
merge(int n1, const int a1[], int n2, const int a2[], int out[])
{
    int i1;
    int i2;
    int iout;

    i1 = i2 = iout = 0;

    while(i1 < n1 || i2 < n2) {
        if(i2 >= n2 || ((i1 < n1) && (a1[i1] < a2[i2]))) {
            /* a1[i1] exists and is smaller */
            out[iout++] = a1[i1++];
        }  else {
            /* a1[i1] doesn't exist, or is bigger than a2[i2] */
            out[iout++] = a2[i2++];
        }
    }
}

/* sort a, putting result in out */
/* we call this mergeSort to avoid conflict with mergesort in libc */
void
mergeSort(int n, const int a[], int out[])
{
    int *a1;
    int *a2;

    if(n < 2) {
        /* 0 or 1 elements is already sorted */
        memcpy(out, a, sizeof(int) * n);
    } else {
        /* sort into temp arrays */
        a1 = malloc(sizeof(int) * (n/2));
        a2 = malloc(sizeof(int) * (n - n/2));

        mergeSort(n/2, a, a1);
        mergeSort(n - n/2, a + n/2, a2);

        /* merge results */
        merge(n/2, a1, n - n/2, a2, out);

        /* free the temp arrays */
        free(a1);
        free(a2);
    }
}

#define N (20)

int
main(int argc, char **argv)
{
    int a[N];
    int b[N];
    int i;

    for(i = 0; i < N; i++) {
        a[i] = N-i-1;
    }

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    putchar('\n');

    mergeSort(N, a, b);

    for(i = 0; i < N; i++) {
        printf("%d ", b[i]);
    }
    putchar('\n');

    return 0;
}

examples/sorting/mergesort.c

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

The reason that we can’t easily transform this into an iterative version is that the mergeSort function is not tail-recursive: not only does it call itself twice, but it also needs to free the temporary arrays at the end. Because the algorithm has to do these tasks on the way back up the stack, we need to keep the stack around to track them.

Asymptotic complexity of recursive functions

One issue with a recursive functions is that it becomes harder to estimate its asymptotic complexity. Unlike loops, where we can estimate the cost by simply multiplying the number of iterations by the cost of each iteration, the cost of a recursive function depends on the cost of its recursive calls. This would make it seem that we would need to be able to compute the cost of the function before we could compute the cost of the function.

Fortunately, for most recursive functions, the size of the input drops whenever we recurse. So the cost can be expressed in terms of a recurrence, a formula for the cost T(n) on an input of size n in terms of the cost on smaller inputs. Some examples:

T(n) = O(1) + T(n/2)

This is the cost of binary search. To search an array of n elements, look up the middle element (O(1) time) and, in the worst case, recurse on an array of n/2 elements.

T(n) = 2T(n/2) + O(n)

This is the cost of mergesort. Sort two half-size arrays recursively, then merge them in O(n) time.

T(n) = O(1) + T(n − 1)

This is the cost of most simple loops, if we think of them as a recursive process. Do O(1) work on the first element, then do T(n − 1) work on the rest.

There are standard tools for solving many of the recurrences that arise in common algorithms, but these are not usually needed for our purposes, since there are only a handful of recurrences that are likely to come up in practice and we already solved most of them. Here is a table of some of the more common possibilities: