Implementações da Sequência de Fibonacci em Python

O número de Fibonacci [1] ou sequência de Fibonacci é um exemplo clássico utilizado na computação para demonstração de recursividade.

No entanto, existem diversas implementações e geralmente com uma performance melhor que a versão recursiva:

Versão recursiva:

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

for x in range(10):
    fibonacci(x)

Versão iterativa:

def fibonacci(n):
    a,b = 0,1
    for i in range(n):
        a,b = b,a+b
    return a

for x in range(10):
    fibonacci(x)

Versão iterativa com "generators" [3]:

def fibonacci():
    a, b = 0, 1
    while True:
       yield a
       a,b = b,a+b

f = fibonacci3()
for x in range(10):
    f.next()

Versão com "cálculo da proporção áurea (phi)" [4]

from math import log
phi = (1 + 5**0.5) / 2

def fibonacci(n):
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

for x in range(10):
    fibonacci(x)

Versão recursiva/funcional:

fibonacci = lambda n,a=1,b=1:[b,0][n>0] or fibonacci(n-1,b,a+b)

for x in range(10):
    fibonacci(x)

Utilizando o módulo "timeit" [5] repetindo 3 vezes e executando 1000 vezes cada função temos a lista de performance:

Versão recursiva: 0.635288953781
Versão iterativa: 0.0393660068512
Versão iterativa com "generators": 0.0163049697876
Versão com "cálculo da proporção áurea (phi)": 0.0362870693207
Versão recursiva/funcional: 0.100222110748

De longe o pior resultado é a versão recursiva como esperado, e o melhor resultado é da versão iterativa com "generators".

[1] - http://en.wikipedia.org/wiki/Fibonacci_number
[2] - http://pt.wikipedia.org/wiki/Recursividade
[3] - http://www.python.org/dev/peps/pep-0255/
[4] - http://en.wikipedia.org/wiki/Golden_ratio
[5] - http://docs.python.org/lib/module-timeit.html