Este es un algoritmo muy rápido y puede encontrar el n-ésimo número de Fibonacci mucho más rápido que el enfoque iterativo simple presentado en otras respuestas, aunque es bastante avanzado:

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

Puedes leer más sobre las matemáticas involucradas aquí.

Python no optimiza la recursión de cola, por lo que la mayoría de las soluciones presentadas aquí fallarán con Error: maximum recursion depth exceeded in comparison si n es demasiado grande (y por grande, me refiero a 1000).

El límite de recursión se puede aumentar, pero hará que Python se bloquee en el desbordamiento de la pila en el sistema operativo.

Tenga en cuenta la diferencia en el rendimiento entre fib_memo / fib_local y fib_lru / fib_local_exc: La caché de LRU es mucho más lenta y ni siquiera se completó, porque ya produce un error de tiempo de ejecución para n = ~500:

import functools
from time import clock
#import sys
#sys.setrecursionlimit()

@functools.lru_cache(None)
def fib_lru(n):
    if n < 2:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

def fib_memo(n, computed = {0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
    return computed[n]

def fib_local(n):
    computed = {0: 0, 1: 1}
    def fib_inner(n):
        if n not in computed:
            computed[n] = fib_inner(n-1) + fib_inner(n-2)
        return computed[n]
    return fib_inner(n)

def fib_local_exc(n):
    computed = {0: 0, 1: 1}
    def fib_inner_x(n):
        try:
            computed[n]
        except KeyError:
            computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
        return computed[n]

    return fib_inner_x(n)

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

def benchmark(n, *args):
    print("-" * 80)
    for func in args:
        print(func.__name__)
        start = clock()
        try:
            ret = func(n)
            #print("Result:", ret)
        except RuntimeError as e:
            print("Error:", e)
        print("Time:", "{:.8f}".format(clock() - start))
        print()

benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)

Resultados:

fib_iter
Time: 0.00008168

fib_memo
Time: 0.00048622

fib_local
Time: 0.00044645

fib_local_exc
Time: 0.00146036

fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552

La solución iterativa es de lejos la más rápida y no daña la pila ni siquiera durante n=100k (0,162 segundos). No devuelve los números intermedios de Fibonacci de hecho.

Si desea calcular el n número incluso de Fibonacci, podría adaptar el enfoque iterativo de la siguiente manera:

def fib_even_iter(n):
    a, b = 0, 1
    c = 1
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            c += 1
    return a

O si usted está interesado en cada número par en el camino, utilice un generador :

def fib_even_gen(n):
    a, b = 0, 1
    c = 1
    yield a
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            yield a
            c += 1
    return a

for i, f in enumerate(fib_even_gen(100), 1):
    print("{:3d}.  {:d}".format(i, f))

Resultado:

  1.  0
  2.  2
  3.  8
  4.  34
  5.  144
  6.  610
  7.  2584
  8.  10946
  9.  46368
 10.  196418
 11.  832040
 12.  3524578
 13.  14930352
 14.  63245986
 15.  267914296
 16.  1134903170
 17.  4807526976
 18.  20365011074
 19.  86267571272
 20.  365435296162
 21.  1548008755920
 22.  6557470319842
 23.  27777890035288
 24.  117669030460994
 25.  498454011879264
 26.  2111485077978050
 27.  8944394323791464
 28.  37889062373143906
 29.  160500643816367088
 30.  679891637638612258
 31.  2880067194370816120
 32.  12200160415121876738
 33.  51680708854858323072
 34.  218922995834555169026
 35.  927372692193078999176
 36.  3928413764606871165730
 37.  16641027750620563662096
 38.  70492524767089125814114
 39.  298611126818977066918552
 40.  1264937032042997393488322
 41.  5358359254990966640871840
 42.  22698374052006863956975682
 43.  96151855463018422468774568
 44.  407305795904080553832073954
 45.  1725375039079340637797070384
 46.  7308805952221443105020355490
 47.  30960598847965113057878492344
 48.  131151201344081895336534324866
 49.  555565404224292694404015791808
 50.  2353412818241252672952597492098
 51.  9969216677189303386214405760200
 52.  42230279526998466217810220532898
 53.  178890334785183168257455287891792
 54.  757791618667731139247631372100066
 55.  3210056809456107725247980776292056
 56.  13598018856492162040239554477268290
 57.  57602132235424755886206198685365216
 58.  244006547798191185585064349218729154
 59.  1033628323428189498226463595560281832
 60.  4378519841510949178490918731459856482
 61.  18547707689471986212190138521399707760
 62.  78569350599398894027251472817058687522
 63.  332825110087067562321196029789634457848
 64.  1409869790947669143312035591975596518914
 65.  5972304273877744135569338397692020533504
 66.  25299086886458645685589389182743678652930
 67.  107168651819712326877926895128666735145224
 68.  453973694165307953197296969697410619233826
 69.  1923063428480944139667114773918309212080528
 70.  8146227408089084511865756065370647467555938
 71.  34507973060837282187130139035400899082304280
 72.  146178119651438213260386312206974243796773058
 73.  619220451666590135228675387863297874269396512
 74.  2623059926317798754175087863660165740874359106
 75.  11111460156937785151929026842503960837766832936
 76.  47068900554068939361891195233676009091941690850
 77.  199387062373213542599493807777207997205533596336
 78.  844617150046923109759866426342507997914076076194
 79.  3577855662560905981638959513147239988861837901112
 80.  15156039800290547036315704478931467953361427680642
 81.  64202014863723094126901777428873111802307548623680
 82.  271964099255182923543922814194423915162591622175362
 83.  1152058411884454788302593034206568772452674037325128
 84.  4880197746793002076754294951020699004973287771475874
 85.  20672849399056463095319772838289364792345825123228624
 86.  87571595343018854458033386304178158174356588264390370
 87.  370959230771131880927453318055001997489772178180790104
 88.  1571408518427546378167846658524186148133445300987550786
 89.  6656593304481317393598839952151746590023553382130993248
 90.  28197781736352815952563206467131172508227658829511523778
 91.  119447720249892581203851665820676436622934188700177088360
 92.  505988662735923140767969869749836918999964413630219877218
 93.  2143402371193585144275731144820024112622791843221056597232
 94.  9079598147510263717870894449029933369491131786514446266146
 95.  38461794961234640015759308940939757590587318989278841661816
 96.  162926777992448823780908130212788963731840407743629812913410
 97.  690168906931029935139391829792095612517948949963798093315456
 98.  2923602405716568564338475449381171413803636207598822186175234
 99.  12384578529797304192493293627316781267732493780359086838016392
100.  52461916524905785334311649958648296484733611329035169538240802

Time: 0.00698620

Esos son los primeros 100 números incluso de Fibonacci en ~7ms e incluye la sobrecarga de impresión a terminal (fácil de subestimar en Windows).

Basado en el hecho de que fib(n) = fib(n-1)+fib(n-2), la solución directa es

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

Sin embargo, el problema aquí es que algunos valores se calculan varias veces, y por lo tanto es muy ineficiente. La razón se puede ver en este bosquejo:

Esencialmente, cada llamada recursiva a la función fib tiene que calcular todos los números anteriores de fibonacci para su propio uso. Por lo tanto, el valor más calculado será fib (1) ya que tiene que aparecer en todos los nodos de la hoja de la árbol mostrado por la respuesta de @kqr. La complejidad de este algoritmo es el número de nodos del árbol, que es $O (2^n)$.

Ahora una mejor manera es hacer un seguimiento de dos números, el valor actual y el valor anterior, por lo que cada llamada no tiene que calcular todos los valores anteriores. Este es el segundo algoritmo en el croquis, y se puede implementar de la siguiente manera

def fib(n):
   if (n==0):
       return(0,1)
   elif (n==1):
       return(1,1)
   else:
       a,b = fib(n-1)
       return(b,a+b)

La complejidad de este algoritmo es lineal linear O (n) {, y algunos ejemplos serán

>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)

Solución en R, benchmark calcula de 1 a 1000a serie de números de Fibonacci en 1.9 segundos. Sería mucho más rápido en C++ o Fortran, de hecho, desde que escribí el post inicial, escribí una función equivalente en C++ que se completó en un impresionante 0.0033 segundos, incluso python completado en 0.3 segundos.

#Calculate Fibonnaci Sequence
fib <- function(n){
  if(n <= 2)
    return(as.integer(as.logical(n)))
  k = as.integer(n/2)
  a = fib(k + 1)
  b = fib(k)
  if(n %% 2 == 1)
    return(a*a + b*b)
  return(b*(2*a - b))
}

#Function to do every fibonacci number up to nmax
doFib <- function(nmax = 25,doPrint=FALSE){
    res = sapply(0:abs(nmax),fib)
    if(doPrint)
        print(paste(res,collapse=","))
    return(res)
}

#Benchmark
system.time(doFib(1000))

#user  system elapsed 
#  1.874   0.007   1.892 

Basé esto en un artículo sobre números de Fibonacci en Wikipedia. La idea es evitar bucles y recursiones y simplemente calcular el valor según sea necesario.

Al no ser un mago de las matemáticas, seleccionó una de las fórmulas y la renderizó en código y la ajustó hasta que los valores salieran bien.

import cmath

def getFib(n):
    #Given which fibonacci number we want, calculate its value
    lsa = (1 / cmath.sqrt(5)) * pow(((1 + cmath.sqrt(5)) / 2), n)
    rsa = (1 / cmath.sqrt(5)) * pow(((1 - cmath.sqrt(5)) / 2), n)
    fib = lsa-rsa
    #coerce to real so we can round the complex result
    fn = round(fib.real) 
    return fn 

#Demo using the function
s = ''
for m in range(0,30):
    s = s + '(' + str(m) + ')' + str(getFib(m)) + ' '

print(s)

La solución no 2 de Kqr es mi favorita definitiva.
Sin embargo, en este caso específico estamos perdiendo todos nuestros cálculos entre llamadas consecuentes dentro de la comprensión de la lista:

list2 = [i for i in list1 if fib(i) % 2 == 0]

, así que decidí ir un paso más allá y recordarlo entre los pasos del bucle de la siguiente manera:

def cache_fib(ff):
    comp = {0: 0, 1: 1}

    def fib_cached(n, computed=comp):
        return ff(n, computed)
    return fib_cached


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

Cualquier problema como este tardará mucho tiempo en ejecutarse si hay muchos niveles de recursividad. La definición recursiva es buena para codificar el problema de una manera que se pueda entender fácilmente, pero si necesita que se ejecute más rápido, una solución iterativa como la respuesta en este hilo será mucho más rápido.

Calcular recursivamente Fibonacci será más ineficiente que hacerlo iterativamente. Mi recomendación es:

Tómese el tiempo para crear una clase Fibonacci como un iterador, y haga los cálculos de forma independiente para cada elemento en el índice, tal vez con algunos @memoize decorador (y también aquí) para almacenar en caché todos los cálculos anteriores.

Espero que esto ayude!

Una forma rápida es calcular el número fib(n/2) recursivamente:

fibs = {0: 0, 1: 1}
def fib(n):
    if n in fibs: return fibs[n]
    if n % 2 == 0:
        fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
        return fibs[n]
    else:
        fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
        return fibs[n]

from time import time
s=time()
print fib(1000000)
print time()-s

Haskell 1 liner: -

fibs = 0 : (f 1 1) where f a b = a : f b (a+b)

Este código es extremadamente eficiente y calcula números de Fibonacci hasta (10^1000) en menos de un segundo ! Este código también será útil para este problema en el Proyecto Euler.

Para encontrar la suma de los primeros n números de fibonacci con valor par directamente, coloque 3n + 2 en su método favorito para calcular eficientemente un solo número de fibonacci, decrementar en uno y dividir en dos (fib((3*n+2) - 1)/2)). ¿Cómo sobrevivieron los maniquíes de matemáticas antes de OEIS?

Puede usar la ecuación con raíces cuadradas para calcular esto si no usa aritmética de coma flotante, pero mantenga un registro de los coeficientes de alguna otra manera a medida que avanza. Esto da un algoritmo exacto de tiempo esencialmente constante para los números de Fibonacci:

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55

Esta es una versión mejorada de Fibonacci donde calculamos Fibonacci de número solo una vez:

dicFib = { 0:0 ,1 :1 }
iterations = 0
def fibonacci(a):
    if  (a in dicFib):      
        return dicFib[a]    
    else :
        global iterations               
        fib = fibonacci(a-2)+fibonacci(a-1)
        dicFib[a] = fib
        iterations += 1
        return fib

print ("Fibonacci of 10 is:" , fibonacci(10))
print ("Fibonacci of all numbers:" ,dicFib)
print ("iterations:" ,iterations)

# ('Fibonacci of 10 is:', 55)
# ('Fibonacci of all numbers:', {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55})
# ('iterations:', 9)

Aquí estamos almacenando Fibonacci de cada número en el diccionario. Así que puedes ver que calcula solo una vez para cada iteración y para Fibonacci(10) es solo 9 veces.

Aunque una respuesta tardía, pero podría ser útil

fib_dict = {}

def fib(n): 
    try:
        return fib_dict[n]
    except:
        if n<=1:
            fib_dict[n] = n
            return n
        else:
            fib_dict[n] = fib(n-1) + fib (n-2)
            return fib(n-1) + fib (n-2)

print fib(100)

Esto es mucho más rápido que la forma tradicional

Una solución de O(1)

Resulta que hay una buena fórmula recursiva para la suma de números pares de Fibonacci. El enésimo término en la secuencia de sumas de números de Fibonacci pares es S_{n} = 4*S_{n-1} + S_{n-2} + 2 La prueba se deja al lector, pero implica probar 1) los números de Fibo pares son cada tres, 2) la prueba de la fórmula anterior con inducción utilizando la definición de números de Fibo. Usando la lógica de aquí , podemos derivar una fórmula de forma cerrada para esto con un poco esfuerzo:

S_{n} = -1/2 + (1/4 + 3*sqrt(5)/20)*(2+sqrt(5))**n + (1/4 - 3*sqrt(5)/20)*(2-sqrt(5))**n

A pesar de sqrt, esto es integral para integral n, así que esto puede ser convenientemente calculado usando las funciones prácticas de mi respuesta anterior, o usando un paquete como sympy para manejar las raíces exactamente.

import sympy as sp
one = sp.sympify(1) #to force casting to sympy types
k1 = -one/2
k2 = one/4 + 3*sp.sqrt(5)/20
k3 = one/4 - 3*sp.sqrt(5)/20
r1 = one
r2 = 2 + sp.sqrt(5)
r3 = 2 - sp.sqrt(5)
def even_sum_fibo(n):
  #get the nth number in the sequence of even sums of Fibonacci numbers.  If you want the sum of Fibos up to some number m, use n = m/3 (integer division)
  return sp.simplify(k1*r1**n + k2*r2**n + k3*r3**n)

Hay una solución O(1): https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

import math

PHI = (1 + math.sqrt(5)) / 2
SQRT5 = math.sqrt(5)


def fast_fib(n):
    if n < 0:
        raise ValueError('Fibs for negative values are not defined.')
    return round(math.pow(PHI, n) / SQRT5)

Dado el número inicial y el número máximo; creo que la siguiente solución para fibonacci sería interesante. Lo bueno es que no incluye recursión, lo que reduce la carga de memoria.

# starting number is a
# largest number in the fibonacci sequence is b

def fibonacci(a,b):
    fib_series = [a, a]

    while sum(fib_series[-2:]) <=b:
        next_fib = sum(fib_series[-2:])
        fib_series.append(next_fib)

    return fib_series

print('the fibonacci series for the range %s is %s'
      %([3, 27], fibonacci(3, 27)))

the fibonacci series for the range [1, 12] is [3, 3, 6, 9, 15, 24]

int count=0;
void fibbo(int,int);

void main()

{

fibbo(0,1);

    getch();
}

void fibbo(int a,int b)

{

 count++;

 printf(" %d ",a);

if(count<=10)

     fibbo(b,a+b);

else

      return;

}