Properties of bad fibonacci algorithm
- by John Smith
I was looking at the canonical bad fibonacci algorithm the other day:
public static int fib(int n)
{
// Base Case
if (n < 2)
return 1;
else
return fib(n-1) + fib(n-2);
}
I made the interesting observation. When you call fib(n), then for k between 1 and n fib(k) is called precisely fib(n-k+1) times (or fib(n-k) depending on your definition of fib(0) ). Also, fib(0) is called fib(n-k-1) times. This then allows me to find that in fib(100) there are exactly 708449696358523830149 calls to the fib function.
Are there other interesting observations on this function you know of?
