FAQ > An introduction to recursion


Match word(s).

If you have any questions or comments,
please visit us on the Forums.

FAQ > Prelude's Corner > An introduction to recursion

This item was added on: 2004/01/21

Introduction

Recursion is a programming technique where a function calls itself. While this may sound like an error, the design of C/C++ function calls at runtime make it not only legal, but incredibly useful. Recursion is used to break a problem up into smaller, similar problems so that they might be solved easier. The canonical first example of recursion is a function for calculating factorials. A factorial is a number that is defined as

N! = N * (N - 1)!, for N > 0

Factorials are defined recursively, the above formula basically says that The factorial of N is N times the factorial of N - 1 as long as N is greater than 0. In C/C++ we could do this using a loop, like so:


int fact_iterative ( int i )
{
  int ret = 1;

  while ( i > 0 )
    ret *= i--;

  return ret;
}


Simple enough, fact_iterative ( 5 ) executes like this:

5 * 4 * 3 * 2 * 1 = 120

which is the correct answer. We can write a function that is closer to the definition of a factorial by having our function call itself, like this:


int fact_recursive ( int i )
{
  if ( i > 0 )
    return i * fact_recursive ( i - 1 );
  return 1;
}


Notice that fact_recursive calls itself with i - 1 and then multiplies the return value by i. This function is very similar to the factorial definition above, and that makes it easier to check for errors.

Base Cases

Notice that a test for i > 0 is made before the function is called again. This is called the base case, and it is required for every recursive function. Without a base case, the function would not know when to stop calling itself, and you would have an infinite recursion (or until you ran out of stack space). Speaking of stack space, how does recursion work anyway? Good question.

Every time you call a function, a thingy (very technical term) called an activation record is pushed onto the stack. The activation record, also known as a stack frame, contains things such as local variables for the function, arguments, and the address of the previous activation record so that it knows how to return from whence it came. Because of these activation records, two calls to the same function aren't actually the same activation record, that's why recursion works. Each new call to fact_recursive has its own memory, its own argument copies, its own everything.

Because this all works like a stack, each new activation record covers up the previous record. When the function finally reaches the base case and returns, each activation record is popped from the stack until execution finally leaves the first call to fact_recursive. This is called unwinding the stack, you'll hear that term again sometime in your programming careers, but I won't say where. :)

Binary Search

Most recursive solutions will follow the divide and conquer concept. Where one divides the problem in half (and each sub-problem in half) until the solution is obvious. The best example of this is a binary search:


int binsearch ( int *a, int l, int h, int key )
{
  int m;

  m = ( l + h ) / 2;
  if ( a[m] == key )
    return m;
  else if ( l > h )
    return -1;
  else if ( a[m] < key )
    return binsearch ( a, m + 1, h, key );
  else
    return binsearch ( a, l, m - 1, key );
}


By dividing the array in half, it's easy to determine which half the desired element is in. Then that half is divided, and the half that results, and so on until the only option left is a single element. From that single element it is trivial to determine if the search key is in the array. :) I encourage you to play with this function until you fully understand how it works.

Simulating Recursion

Any operation that can be carried out with recursion can also be carried out with an explicit stack, that is, a stack that you write can be used to simulate recursion. Taking the factorial example because I'm too lazy to write a stack based binary search routine, we could come up with something like this:


int fact_stack ( int i )
{
  int stack[5]; /* Assume fact_stack ( 5 ) */
  int top = 0;
  int ret = 1;

  while ( i > 0 )
    stack[top++] = i--;
  while ( top > 0 )
    ret *= stack[--top];

  return ret;
}


It really isn't much different from the iterative version except for the use of a stack. Now, while it's certainly possible to simulate recursion, as evidenced by the above function, it's rarely practical. If you can convert the recursive function to an iterative function easily, there's no point in simulating recursion. If a stack is required for correct operation, such as with an iterative quicksort, the extra work involved makes the iterative approach impractical except in extreme cases of performance.

Tail Recursion

There is one kind of recursion that can easily be converted into iteration, and usually should have been iterative to begin with. This is called tail recursion. Tail recursion is a special case where a single recursive call to the function is at the end of the same function, in other words:


void tail ( int i )
{
  if ( i == 0 )
    return;
  tail ( i - 1 );
}


Tail recursion is usually optimized by compilers, but you can do it yourself simply by turning the recursion into a loop. This is very simple:


void tail ( int i )
{
  while ( i != 0 )
    i--;
}


Performance Issues

Recursion isn't always the best choice. In fact, it isn't the best choice most of the time because both the drastic growing of the stack and the overhead of function calls tends to effect efficiency more than is practical. Some algorithms, such as binary tree traversals and recursive sorting routines are better suited recursively. However, these algorithms have very precise growth needs or would be difficult and awkward to implement iteratively.

Script provided by SmartCGIs