Recursion Pedagogy (or, How to Make Novice Programmers Crash their Machines)

It's fairly common to find programming books that teach recursion using the Fibonacci sequence as the main example. The obvious reasons for this are that the Fibonacci sequence is easy to understand (each value is just the sum of the preceding two values, with the first and second values in the sequence defined to both be 1) and that this simple dependence makes for massively simple recursion calls and tests. The recursive function, in fact, seems almost magical (code fragments usually in C# unless otherwise noted):

int RecursiveFibonacci(int nth)
{
    if (nth < 3)
    {
        return 1;
    }

    return RecursiveFibonacci(nth - 2) + RecursiveFibonacci(nth - 1);
}

That's it. That function will theoretically get you any number in the Fibonacci sequence (well, only up to the 32-bit limit, but that's easy enough to change).

Fibonacci numbers, however, are an incredibly bad candidate for recursion!

The function is short and simple, which is good; very easy to understand, which is better, and so massively inefficient that if you naively test it by asking for, say, the 50th Fibonacci number you're likely to spend some time trying to figure out where the bug is since it appears to have crashed!

What's actually happening, however, is that you're making an insane number of function calls, thus creating an insane number of function stack frames, each taking up at least eight bytes (if you're using 32-bit integers).

Calculating the 50th Fibonacci number by hand requires adding two numbers 48 times. Calculating the 50th Fibonacci number by recursion requires calling that function above 25.2 B-B-B-B-Billion times!! (Which requires more than 200 Gigabytes of memory just for the stack frames.) What's going on here? Well, we're looking at what I call the (w)Rec(k)Fib sequence:

1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973 ...

which looks very much like the Fibonacci sequence:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 ...

Every value in the (w)Rec(k)Fib sequence is twice its Fibonacci counterpart minus one. But that's not the most meaningful way to come up with it; rather, each value is the sum of the previous two (like Fibonacci) plus one more. So where Fibonacci is F(n) = F(n-1) + F(n-2), (w)Rec(k)Fib is w(n) = w(n-1) + w(n-2) + 1. It's also the number of times the recursive function is called to determine its Fibonacci sequence counterpart. When the function is called for, say, the fourth Fibonacci number, that's one call, to which we add the number of calls (3) for the third Fibonacci number and the number of calls (1) for the second Fibonacci number. In other words, we have to call the function far more times (twice minus one) than the value of the number we're seeking. Which means that even with modern processor speeds and memory sizes, and virtual memory, we can take an incredibly long time (or fail altogether). Want to calculate the hundredth Fibonacci number? (It's about 3.5E+20.) If you happen to have access to a computer that can manage a billion function calls per second (more actual operations, of course), it'll take around 22,500 years. But you can probably do it by hand in an hour or so (a couple if you're being careful not to miss a carry).

So, what's the right way to do it? Well, the simplest is through basic iteration, just like you'd do it by hand:

int IterativeFibonacciNumber(int nth)
{
    if (nth < 3)
    {
        return 1;
    }

    int a = 1;
    int b = 1;

    int temp;
    for (int n = 3; n <= nth; n++)
    {
       temp = b;
       b = b + a;
       a = temp;
    }

    return b;
}

It's not nearly as elegant. Nothing about it looks magical. It's not even all that easy to understand, though better variable names would obviously help. But it'll calculate the fiftieth Fibonacci number in about 4 milliseconds on my 2007-vintage laptop, running inside Visual Studio in Debug mode...which is where most of that 4 milliseconds comes from. How do I know? Switch most of the integer variables to long integers, and it'll calculate the 92nd Fibonacci number (the highest storable in a 64-bit integer) in the same 4 milliseconds.

Never, ever, ever use recursion if there's a straightforward way to accomplish the task without it. And, should you conclude that recursion is the way to go, try to at least get a feel for how the function behaves. If, as in this case, you're looking at O(c^n), then you almost certainly need to look again...or conclude that the problem is not practically soluble. (Unless the maximum n is small, of course.)

UPDATE: I should add, of course, that the quickest way is actually to open Excel, type 1 in the top left cell, type 1 again in the cell below it, then type =A1+A2 in the cell below that, and drag down on the box at the bottom-right corner of the cell. You'll get up to the 54th Fibonacci number with the full set of digits. Past that, you'll get floating point values with an ever-decreasing set of digits up to the 1476th Fibonacci number (1.307E+308). If you want the 'real' answer or values beyond that, you're going to have to set up your own kilobit-plus integer (or play with some identities that allow easier calculation of large Fibonacci numbers - see wikipedia).