# Memoization and Recursion in Python

## let’s try to program to find the nth fibonanci number

Here is an example to think about recursion and memoization in Python.

1
2
3
4
5

def fib(n, memo = {0:0, 1:1}):
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]

When we run this function `fib()`

with various values of n:

1
2
3

fib(3), fib(4), fib(6)
>>> (2, 3, 8)

Now let’s look at how long it takes to run this function for a realtively large value, 100:

1
2
3
4
5
6
7

%%time
fib(100)
>>> CPU times: user 0 ns, sys: 0 ns, total: 0 ns
>>> Wall time: 212 µs
>>> 354224848179261915075