Fibonacci is an interesting problem – something resembling the tip of an iceberg.
I have been studying this problem lately, and I got interested in timing out some implementations.
Timeit is a very useful Python module for timing related functionality.
There are 2 ways of using it:
 From the IPython prompt.
In : import timeit
In : tI = timeit.Timer("fib.fibI(10)", "import fibonacci as fib")
In : tI.repeat(2, 4)
Out: [0.00013392966229730519, 2.9327663469302934e-05]
(Adapting Reference  for the example above)
||The timeit module defines one class, Timer, which takes two arguments. Both arguments are strings. The first argument is the statement you wish to time; in this case, we are timing a call to the fibI function with an argument of 10. The second argument to the Timer class is the import statement that sets up the environment for the statement. Internally, timeit sets up an isolated virtual environment, manually executes the setup statement (importing the fibonacci module), then manually compiles and executes the timed statement (calling the fibI function).
||Once you have the Timer object, the easiest thing to do is call timeit(), which calls your function 1 million times and returns the number of seconds it took to do it.
||The other major method of the Timer object is repeat(), which takes two optional arguments. The first argument is the number of times to repeat the entire test, and the second argument is the number of times to call the timed statement within each test. Both arguments are optional, and they default to 3 and 1000000 respectively. The repeat() method returns a list of the times each test cycle took, in seconds.
 From the Command Line.
$ python -m timeit -s "import fibonacci as fib" "fib.fibI(20)"
100000 loops, best of 3: 13.7 usec per loop
 Handling state when making recursive calls.
A few additional insights I had while working on this problem –
- How to effectively handle state when doing recursion ?
- Top-down recursion v/s bottom-up iteration.
- In many cases, bottom up might help. Think about it.
- Resemblance with Dynamic Programming.