Fibonacci, recursion and decorators

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

$$ f(n) := \begin{cases} n &\text{if } n \leq 1\ f(n-1) + f(n-2) &\text{otherwise} \end{cases} $$

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

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

$$ f(n) := \begin{cases} 1 &\text{if } n \leq 1\ f(n-1) + f(n-2) + 1 &\text{otherwise} \end{cases} $$

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):
    a, b = 0, 1
    for i in range(n):
        a, b = a + b, a
    return a

Additional ressources ¶

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