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:
if n==0: return 1
if n==1: return 1
On building an integrated QuantLib/Lua platform on the world's most popular computer.