Properties of bad fibonacci algorithm

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 开发者_如何学Gointeresting observations on this function you know of?

Additional note: I know all the cool stuff about memoization etc... I am NOT asking on how to optimize it.

---

This is a wonderful case for why memoization is a very useful optimization in functions such as Fibonacci.

As you can see, you can reduce the number of function calls from 2*fib(n)-1 to n - which is orders of magnitude better.

Mathematics-wise, the Fibonacci numbers have many other interesting properties.

---

Adding to what Yuval has said...

As well as memoization, it's also worth mentioning the closely related "dynamic programming". Very closely related - personally, I'm not too clear on whether memoization is a special case of dynamic programming or not. Anyway, in this case, the standard iterative solution could be called a dynamic programming solution.

In the iterative solution, when you try to calculate fib(n), you have already calculated the partial solutions fib(n-2) and fib(n-1) so you just re-use those precalculated partial solutions. That it is done in a loop isn't important to dynamic programming. Memoization can be a special case (I'm just not sure whether it's always a special case according to strict definitions). The key point is that each partial solution is remembered, so that it only needs to be calculated once.

---

I'll just toss this more mathematical note in. The big O notation for your algorithm is indeed F(n), but what the heck does that mean compared to O(N^2) or O(NlogN) we normally think about?

Its crazy bad: it has O(e^N) space and time complexity. Mathematically you can show that lim (N-> \inf) F(n) = ((1+\sqrt(5))/2)^N