Fibonnaci using Dynamic Programming

If you read this article on Python profiling and memoization you learned one trick to optimize performance. However, often thinking out-of-the-box can lead to elegant solutions as well. I have to give credits for this article to Jesse Farmer where he described this solution using dynamic programming.

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
       return fibonacci(n-2) + fibonacci(n-1)   

def fibonacci2(n):
    n2, n1 = 0, 1
    for i in range(n-2):
        n2, n1 = n1, n1 + n2
    return n2 + n1

import cProfile
cProfile.run('print fibonacci(25)')
cProfile.run('print fibonacci2(25)')

75025
         242829 function calls (39 primitive calls) in 1.527 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.527    1.527 :1()
 242785/1    1.527    0.000    1.527    1.527 PythonApplication1.py:1(fibonacci)
        2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:1148(write_string)
        2    0.000    0.000    0.001    0.000 visualstudio_py_debugger.py:1472(write)
      8/2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:266(probe_stack)
        2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:58(__enter__)
        2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:61(__exit__)
        4    0.000    0.000    0.000    0.000 {_struct.pack}
        2    0.000    0.000    0.000    0.000 {isinstance}
        2    0.000    0.000    0.000    0.000 {len}
        2    0.000    0.000    0.000    0.000 {method 'acquire' of 'thread.lock' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'release' of 'thread.lock' objects}
       10    0.000    0.000    0.000    0.000 {method 'send' of '_socket.socket' objects}
        2    0.000    0.000    0.000    0.000 {method 'write' of 'file' objects}
        2    0.000    0.000    0.000    0.000 {thread.get_ident}


75025
         46 function calls (40 primitive calls) in 0.001 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.001    0.001 :1()
        1    0.000    0.000    0.000    0.000 PythonApplication1.py:9(fibonacci2)
        2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:1148(write_string)
        2    0.000    0.000    0.001    0.000 visualstudio_py_debugger.py:1472(write)
      8/2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:266(probe_stack)
        2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:58(__enter__)
        2    0.000    0.000    0.000    0.000 visualstudio_py_debugger.py:61(__exit__)
        4    0.000    0.000    0.000    0.000 {_struct.pack}
        2    0.000    0.000    0.000    0.000 {isinstance}
        2    0.000    0.000    0.000    0.000 {len}
        2    0.000    0.000    0.000    0.000 {method 'acquire' of 'thread.lock' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'release' of 'thread.lock' objects}
       10    0.000    0.000    0.000    0.000 {method 'send' of '_socket.socket' objects}
        2    0.000    0.000    0.000    0.000 {method 'write' of 'file' objects}
        1    0.000    0.000    0.000    0.000 {range}
        2    0.000    0.000    0.000    0.000 {thread.get_ident}