Recursion and Fibonacci Numbers

Bad Code Leads to Bad Conclusions

Section 6.9 of our textbook gives an example of recursive code to calculate Fibonacci numbers. Cleaning up the style a little, the code looks like this:

unsigned long fib(unsigned int n)
{
    if (n == 0 || n == 1)
    {
      return n;
    }
    else
    {
      return fib(n - 1) + fib(n - 2);
    }
}

Code like this can be found in many textbooks and on many web sites. From this example, the book concludes, on page 356,

"Table 6-2 leads us to the obvious conclusion that a recursive solution to calculate Fibonacci numbers is not realistic for more than 20 numbers."

This conclusion is out and out wrong. The only thing Table 6-2 demonstrates is that the recursive code in Program 6-26 is not usable. That code is a naive implementation of the mathematical equation for Fibonacci numbers. Just because

Fibonacci_n = Fibonacci_{n - 1} + Fibonacci_{n - 2}

doesn't mean fib(n) should call fib(n - 1) and fib(n - 2). In fact, it suggests exactly the opposite.

An Intelligent Recursive Fibonacci Solution

Since Fibonacci_n needs to add the previous two Fibonacci numbers, it makes more sense to define a Fibonacci function that keeps track of the two previous values, i.e., fib2(long n, unsigned long p0, unsigned long p1).

The function fib() handles the base case of 0 and otherwise calls fib2() with the initial 2 values:

unsigned long fib(unsigned int n)
{
    return n == 0 ? 0 : fib2(n, 0, 1);
}

We could catch the n is 1 case too but it's not necessary.

fib2() is equally simple. If n is 1, it just needs to return the most recent Fibonacci value, p1. Otherwise it needs to continue with that value and the sum of the previous two values, like this:

unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1)
{
  return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1);
}

So, the recursive solution is two one-line functions. How efficient is this solution? It calls fib2() N times for an input number N. To see how that compares with the textbook code, compile and run this comparison program, that does both versions, and prints out how many times the recursive function is called in each. As should be clear, the book's conclusion that a recursive solution for Fibonacci is not realistic for more than 20 is simply wrong.

Here are the two versions, side by side, for comparison.

unsigned long fib(unsigned int n)
{
    if (n == 0 || n == 1)
    {
      return n;
    }
    else
    {
      return fib(n - 1) + fib(n - 2);
    }
}

unsigned long fib(unsigned int n)
{
  return n == 0 ? 0 : fib2(n, 0, 1);
}

unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1)
{
  return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1);
}

I'd like to thank Todd Hubers for pointing out a simpler approach than my previous one. A similar solution can be found here.