Here’s another demonstration on how slow recursive functions are. I wrote three functions in C++ that calculates Fibonacci numbers in integer type. Since my computer only supports 32bit integers, I calculated up to the forty-second Fibonacci number, which is 26,7914,296.

Implementations

Our first function uses a recursive definition:

int f1( int n ) {
    if (n < 1)
        return f1(n-1)+f1(n-2);
    else if (n == 1)
        return 1;
    else
        return 0;
}

The second function uses the closed form of the Fibonacci number. Although fast, this function doesn’t necessarily give you the right answer due to rounding errors:

int f2( int n ) {
    double sqrt5 = sqrt((double)5);
    return (pow((1 + sqrt5) / 2,n) - pow((1 - sqrt5) / 2,n)) / sqrt5;
}

And finally, the third function uses simple addition:

int f3( int n ) {
    int v_prev = 1;
    int v_beforeprev = 0;
    int v = 1;

    if (n == 0)
        return 0;
    while (--n) {
        v = v_prev + v_beforeprev;
        v_beforeprev = v_prev;
        v_prev = v;
    }

    return v;
}

Performance Comparisons

I first measured the time each function took to calculate Fibonacci numbers from 0 to 42. Note that all results reported here are obtained on a machine with an AMD Athlon 64 processor. The results show that you should never use the recursive version:

If thought I made some mistake in my program and didn’t really execute f2 and f3 functions properly, take a look at the followings results, in which f2 and f3 did the same calculation 1 million times:

These results imply that f2 is $$2.99\times {10}^6$$ times faster than f1 and f3 is $$8.27\times {10}^6$$ times faster than f1. Moreover, f3 is about 2.77 times faster than f2.

Note that f2 is much faster in calculating a very large Fibonacci numbers such as 100th Fibonacci number although it is nonsensical to use any one of functions written above since each function converts the results into a 32-bit integer. Nevertheless, this tiny experiment indicates how reckless use of recursion could go wrong.