Python: scriviamo un generatore di Fibonacci ricorsivo (e poi iterativo) ed analizziamone la complessità asintotica

Tralasciando la parte matematica su cui potete trovare un’esauriente (ed interessante) spiegazione su Wikipedia, la serie di Fibonacci si definisce:

F(n) = F(n-1) + F(n-2)

per n > 1, e F(1) = 1 e F(0) = 0

Scriviamo un generatore di questa serie in Python:

#!/usr/bin/python

# fib(n) = fib(n-1)+fib(n-2)
# fib(0) = 0
# fib(1) = 1
# fib(2) = 1
# fib(3) = 2
# fib(4) = 3
# fib(5) = 5
# fib(6) = 8
# ...

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

Abbiamo utilizzato un’implementazione ricorsiva; il vero problema di quest’implementazione è subito chiaro: la complessità O(n^2) data dalla ricorsione e dalle tail-call sullo stack (per n molto grande).
Decidiamo allora di scriverne una versione equivalente ma iterativa, in modo da eliminare il problema della complessità:

def fibnr(n):
    fn1 = 1;
    fn2 = 0;
    fib = 0;
    i = 2;
    if n == 0:
         return 0;
    if n == 1:
         return 1;

    while (i <= n):
        fib = fn1 + fn2
        tmp = fn1
        fn1 = fib
        fn2 = tmp
        i += 1
    return fib

La vera complessità questa volta, sta nella testa del programmatore: è molto importante, infatti, scrivere nel modo più preciso possibile il corpo del while. Inoltre, è necessario implementare uno swap di variabile per tenere traccia della storicità della serie (per semplicità qui non ho usato lo swap di due variabili senza una variabile temporanea che ho presentato nei post precedenti). La complessità di questa soluzione iterativa è O(n).

Implementando una sorta di controllo automatico (tramite assert), possiamo capire che la soluzione iterativa è equivalente alla soluzione ricorsiva, ma sappiamo anche che è più veloce e lineare (grazie all’analisi asintotica che abbiamo realizzato):

#!/usr/bin/python

# fib(n) = fib(n-1)+fib(n-2)
# fib(0) = 0
# fib(1) = 1
# fib(2) = 1
# fib(3) = 2
# fib(4) = 3
# fib(5) = 5
# fib(6) = 8
# ...

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

def fibnr(n):
    fn1 = 1;
    fn2 = 0;
    fib = 0;
    i = 2;
    if n == 0:
         return 0;
    if n == 1:
         return 1;

    while (i <= n):
        fib = fn1 + fn2
        tmp = fn1
        fn1 = fib
        fn2 = tmp
        i += 1
    return fib

if __name__ == '__main__':
    for i in xrange(21):
        print i, ',', fib(i), '|', fibnr(i)
        assert (fib(i) == fibnr(i))