# Fibonacci Numbers in C/C++

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:

function 1st trial (ms) 2nd trial (ms) 3rd trial (ms) Average (ms)
f1 73497 74589 76209 74765
f2 0 0 0 0
f3 0 0 0 0

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:

function 1st trial (ms) 2nd trial (ms) 3rd trial (ms) Average (ms)
f2 24918 24587 25625 25043
f3 9053 8894 9160 9036

These results imply that f2 is $2.99×{10}^{6}$ times faster than f1 and f3 is $8.27×{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.