Fibonacci observation

The highly inefficient fibonacci algorithm is still quite interesting.

When computing fib(n), for k less than n fib(k) is called fib(n-k) times, except when k is 0. This is called n-2 times. The total number of calls for fib(n) is

[sum (for k less than n) fib(k)]+fib(n-2)


Quick python script to check:

d={}

def fib(n):
if d.has_key(n):
d[n]=d[n]+1
else:
d[n]=1
if n==0: return 1
if n==1: return 1
return fib(n-1)+fib(n-2)