fibonacci (recursive with memoization )

count_ipython.log

In [28]: paste

def count(c = []):
    c.append(len(c))
    return c
## -- End pasted text --

In [29]: count()
Out[29]: [0]

In [30]: count()
Out[30]: [0, 1]

In [31]: count()
Out[31]: [0, 1, 2]

In [32]: count()
Out[32]: [0, 1, 2, 3]

In [33]: count()
Out[33]: [0, 1, 2, 3, 4]

In [34]: count([5])
Out[34]: [5, 1]

In [35]: count()
Out[35]: [0, 1, 2, 3, 4, 5]

In [36]: count([0])
Out[36]: [0, 1]

In [37]: count()
Out[37]: [0, 1, 2, 3, 4, 5, 6]

fib_ipython.log

In [1]: paste

def fib(n, fibs=[1, 1]):
    if n >= len(fibs):
        fibs.append(fib(n - 2) + fib(n - 1))
    return fibs[n]
## -- End pasted text --

In [2]: fib(0)
Out[2]: 1

In [3]: fib(1)
Out[3]: 1

In [4]: fib(2)
Out[4]: 2

In [5]: fib(10)
Out[5]: 89

In [6]: fib(20)
Out[6]: 10946

In [7]: [fib(n) for n in range(15) ]
Out[7]: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

fibonacci.py

def fib(n, fibs=[1, 1]):
    if n >= len(fibs):
        fibs.append(fib(n - 2) + fib(n - 1))
    return fibs[n]