I think everybody who learned something about recursion has seen the Fibonacci sequence:

The simplest solution to get this number is:

```
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
```

The problem is, of course, that the number of evaluations goes wild. Here is a table of the number of function calls

n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|

calls | 1 | 1 | 3 | 5 | 9 | 15 | 25 | 41 | 67 | 109 | 177 | 21891 |

To be exact, the number of calls of the fib-function is:

This means the dumb function is in \(\mathcal{O}(2^n)\)! (I'm not quite sure, but this I think this is not only time complexity, but also space complexity. I think it is not tail recursive, so the complete stackframe has to be saved.)

## Memorization with decorators

One way to solve the problem much faster (in fact in \(\mathcal{O}(n)\) time and space complexity) by storing values we already calculated.

A very neat way to achieve this are decorators. It might be a common problem that you have a recursive, mathematical function with no side effects. So you can write a wrapper that checks if the value has already been calculated. If not, the function proceeds as usual. It it has already been calculated, you can simply look it up:

```
def memoize(obj):
cache = {}
def memoizer(*args, **kwargs):
if args not in cache:
cache[args] = obj(*args, **kwargs)
return cache[args]
return memoizer
@memoize
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
```

Notice that I've only added `@memoize`

over the function definiton of `fib`

! I love Python ☺

By the way, this formula has also some limitations. Python has a fixed maximum recursion depth. So `fib(332)`

worked fine, but `fib(333)`

gave:

```
RuntimeError: maximum recursion depth exceeded in comparison
```

You can get around this limitation by successive calls of fib:

```
# Call to fill array
fib(332)
# The number of recursive steps is now much smaller:
print(fib(500))
```

That gave 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125. A pretty big number.

## Formula of Moivre-Binet

The formula of Moivre-Binet gives a closed form for calculating fibonacci numbers:

\(\varphi = \frac{\sqrt{5}+1}{2}\) \(\psi = 1 - \varphi\) \(f(n) = \frac{\varphi^n - \psi^n}{\phi - \psi}\)

Although this is mathematically exact, it will not work on computers due to a fixed floating point precision. Lets check how long it works:

```
#!/usr/bin/env python
import functools
def memoize(obj):
cache = {}
@functools.wraps(obj)
def memoizer(*args, **kwargs):
if args not in cache:
cache[args] = obj(*args, **kwargs)
return cache[args]
return memoizer
@memoize
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
def moivreBinet(n):
phi = (5**0.5+1)/2
psi = 1 - phi
return int((phi**n - psi**n)/(phi - psi))
from itertools import count
for i in count(0):
exact = fib(i)
constTime = moivreBinet(i)
if exact != constTime:
print(("The %i-th fibonacci number is %i. Moivre-Binet "
+ "gives due to precicion error %i (delta=%i).")
% (i, exact, constTime, abs(exact-constTime)))
break
```

So the answer is:

The 72-th fibonacci number is 498454011879264. Moivre-Binet gives due to precicion error 498454011879265 (delta=1).

This is a reason to prefer the \(\mathcal{O}(n)\) solution over the \(\mathcal{O}(1)\) solution. If you're only exact for 72 numbers, you could also simply store them. Looking number up form an array is always faster than any calculation.

## Very high numbers

The following solution is fast and works 0.075 seconds for the 20000 Fibonacci number (which has 4180 digits).

```
def fib(n):
def accFib(n, Nm2=0, Nm1=1):
for i in range(n):
Nm2, Nm1 = Nm1, Nm1+Nm2
return Nm2
return accFib(n)
```

## Additional ressources

The article on literate programs is worth reading. They show some very different programs that calculate Fibonacci numbers.