Originalmente había codificado el programa incorrectamente. En lugar de devolver los números de Fibonacci entre un rango (es decir, startNumber 1, endNumber 20 debería = solo aquellos números entre 1 y 20), he escrito para que el programa muestre todos los números de Fibonacci entre un rango (ie. StartNumber 1, endNumber 20 muestra = primeros 20 números de Fibonacci). Pensé que tenía un código seguro. Tampoco veo por qué sucede esto.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

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

print map(fib, range(startNumber, endNumber))

Alguien señaló en mi Parte II (que estaba cerrada por ser un duplicado - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) que yo necesita pasar startNumber y endNumber a través de un generador usando un ciclo while. ¿Alguien puede señalarme la dirección de cómo hacer esto? Cualquier ayuda es bienvenida.

Soy un programador de aprendizaje y me he encontrado con un poco de confusión. Se me pide que escriba un programa que calcule y muestre la secuencia de Fibonacci por un número de inicio y un número de finalización ingresados ​​por el usuario (es decir, número de inicio = 20 número de finalización = 100 y mostrará solo los números entre ese rango). El truco es usarlo de manera inclusiva (¿qué no sé cómo hacer en Python? ¿Supongo que esto significa usar un rango inclusivo?).

Lo que tengo hasta ahora no es una codificación real, sino más bien:

• Escribe la fórmula de secuencia de Fib hasta infinito
• Muestra startNumber to endNumber solo de la secuencia Fib.

No tengo idea por dónde empezar y estoy pidiendo ideas o ideas sobre cómo escribir esto. También he tratado de escribir la secuencia de Fibra forumla pero también me pierdo en eso.

Hay mucha información sobre la secuencia de Fibonacci en Wikipedia y Wolfram . Mucho más de lo que pueda necesitar. De todos modos, es bueno aprender a usar estos recursos para encontrar (lo más rápido posible) lo que necesita.

Escribe la fórmula de secuencia de Fib hasta infinito

En matemáticas, se da de forma recursiva:

En programación, infinito no existe. Puede usar una forma recursiva traduciendo la forma matemática directamente en su idioma, por ejemplo, en Python se convierte en:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Pruébelo en su idioma favorito y vea que este formulario requiere mucho tiempo a medida que n crece. De hecho, esto es O (2 ⁿ ) en el tiempo.

Continúa en los sitios que te vinculé y verás esto (en wolfram ):

Este es bastante fácil de implementar y muy, muy rápido de calcular, en Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

Otra forma de hacerlo es siguiendo la definición (de wikipedia ):

El primer número de la secuencia es 0, el segundo número es 1, y cada número subsiguiente es igual a la suma de los dos números anteriores de la secuencia misma, produciendo la secuencia 0, 1, 1, 2, 3, 5, 8 etc.

Si su idioma admite iteradores, puede hacer algo como:

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

Muestra startNumber to endNumber solo de la secuencia Fib.

Una vez que sepa cómo generar números de Fibonacci, solo tiene que recorrer los números y verificar si verifican las condiciones dadas.

Suponga que ahora escribió af (n) que devuelve el enésimo término de la secuencia de Fibonacci (como el que tiene sqrt (5))

En la mayoría de los idiomas puedes hacer algo como:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

En python, usaría la forma de iterador y buscaría:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

Mi sugerencia es aprender a leer lo que necesitas. El Proyecto Euler (google for it) te entrenará para hacerlo: P ¡Buena suerte y diviértete!

Generador pitónico eficiente de la secuencia de Fibonacci

Encontré esta pregunta al intentar obtener la generación Pythonic más corta de esta secuencia (más tarde me di cuenta de que había visto una similar en una Propuesta de Mejora de Python ), y no he notado que nadie más haya encontrado mi solución específica (aunque la respuesta principal se acerca, pero aún menos elegante), así que aquí está, con comentarios que describen la primera iteración, porque creo que eso puede ayudar a los lectores a comprender:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

y uso:

for index, fibonacci_number in zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

huellas dactilares:

  0:   0
  1:   1
  2:   1
  3:   2
  4:   3
  5:   5
  6:   8
  7:  13
  8:  21
  9:  34
 10:  55

(Para fines de atribución, recientemente noté una implementación similar en la documentación de Python en los módulos, incluso usando las variables ay b, que ahora recuerdo haber visto antes de escribir esta respuesta. Pero creo que esta respuesta demuestra un mejor uso del lenguaje).

Implementación definida recursivamente

La Enciclopedia en línea de secuencias enteras define la secuencia de Fibonacci recursivamente como

F (n) = F (n-1) + F (n-2) con F (0) = 0 y F (1) = 1

Definir sucintamente esto de forma recursiva en Python se puede hacer de la siguiente manera:

def rec_fib(n):
    '''inefficient recursive function as defined, returns Fibonacci number'''
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

Pero esta representación exacta de la definición matemática es increíblemente ineficiente para números mucho mayores que 30, porque cada número que se calcula también debe calcular para cada número debajo de él. Puede demostrar lo lento que es utilizando lo siguiente:

for i in range(40):
    print(i, rec_fib(i))

Recursión memorable para la eficiencia

Se puede memorizar para mejorar la velocidad (este ejemplo aprovecha el hecho de que un argumento de palabra clave predeterminado es el mismo objeto cada vez que se llama a la función, pero normalmente no usaría un argumento predeterminado mutable por exactamente este motivo):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Descubrirá que la versión memorable es mucho más rápida y superará rápidamente su profundidad máxima de recursión antes de que pueda siquiera pensar en levantarse para tomar un café. Puede ver cuánto más rápido es visualmente haciendo esto:

for i in range(40):
    print(i, mem_fib(i))

(Puede parecer que podemos hacer lo siguiente, pero en realidad no nos permite aprovechar el caché, porque se llama a sí mismo antes de llamar a setdefault).

def mem_fib(n, _cache={}):
    '''don't do this'''
    if n > 1:  
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Generador definido recursivamente:

Como he estado aprendiendo Haskell, me encontré con esta implementación en Haskell:

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

Lo más cerca que creo que puedo llegar a esto en Python en este momento es:

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

Esto lo demuestra:

[f for _, f in zip(range(999), fib())]

Sin embargo, solo puede subir hasta el límite de recurrencia. Por lo general, 1000, mientras que la versión de Haskell puede llegar a los cientos de millones, aunque utiliza los 8 GB de memoria de mi computadora portátil para hacerlo:

> length $ take 100000000 fib 
100000000

Consumir el iterador para obtener el enésimo número de Fibonacci

Un comentarista pregunta:

Pregunta para la función Fib () que se basa en el iterador: ¿qué sucede si desea obtener el enésimo, por ejemplo, el décimo número de fib?

La documentación de itertools tiene una receta para esto:

from itertools import islice

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

y ahora:

>>> nth(fib(), 10)
55

¿Por qué no simplemente hacer lo siguiente?

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))

La idea detrás de la secuencia de Fibonacci se muestra en el siguiente código de Python:

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

Esto significa que fib es una función que puede hacer una de tres cosas. Define fib (1) == 1, fib (0) == 0 y fib (n) como:

fib (n-1) + fib (n-2)

Donde n es un entero arbitrario. Esto significa que fib (2), por ejemplo, se expande a la siguiente aritmética:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

Podemos calcular fib (3) de la misma manera con la aritmética que se muestra a continuación:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

Lo importante a tener en cuenta aquí es que fib (3) no se puede calcular sin calcular fib (2), que se calcula conociendo las definiciones de fib (1) y fib (0). Tener una función que se llama a sí misma como lo hace la función de Fibonacci se llama recursión, y es un tema importante en la programación.

Esto suena como una tarea, así que no voy a hacer la parte inicial / final por ti. Sin embargo, Python es un lenguaje maravillosamente expresivo para esto, por lo que debería tener sentido si comprende las matemáticas y, con suerte, le enseñará sobre la recursividad. ¡Buena suerte!

Editar: Una posible crítica de mi código es que no utiliza el rendimiento de la función Python súper práctica, lo que hace que la función fib (n) sea mucho más corta. Sin embargo, mi ejemplo es un poco más genérico, ya que no muchos lenguajes fuera de Python tienen rendimiento.

Complejidad del tiempo:

La función de almacenamiento en caché reduce la forma normal de calcular las series de Fibonacci de O (2 ^ n) a O (n) al eliminar las repeticiones en el árbol recursivo de la serie de Fibonacci:

Código:

import sys

table = [0]*1000

def FastFib(n):
    if n<=1:
        return n
    else:
        if(table[n-1]==0):
            table[n-1] = FastFib(n-1)
        if(table[n-2]==0):
            table[n-2] = FastFib(n-2)
        table[n] = table[n-1] + table[n-2]
        return table[n]

def main():
    print('Enter a number : ')
    num = int(sys.stdin.readline())
    print(FastFib(num))

if __name__=='__main__':
    main()

Esto es bastante eficiente, utilizando operaciones aritméticas básicas O (log n).

def fib(n):
    return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n)

Éste utiliza operaciones aritméticas básicas O (1), pero el tamaño de los resultados intermedios es grande y, por lo tanto, no es del todo eficiente.

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

Éste calcula X ^ n en el anillo polinomial Z [X] / (X ^ 2 - X - 1) usando la exponenciación por cuadratura. El resultado de ese cálculo es el polinomio Fib (n) X + Fib (n-1), del cual se puede leer el enésimo número de Fibonacci.

Nuevamente, esto usa operaciones aritméticas O (log n) y es muy eficiente.

def mul(a, b):
        return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1]

def fib(n):
        x, r = (1, 0), (0, 1)
        while n:
                if n & 1: r = mul(r, x)
                x = mul(x, x)
                n >>= 1
        return r[0]

Código canónico de Python para imprimir la secuencia de Fibonacci:

a,b=1,1
while True:
  print a,
  a,b=b,a+b       # Could also use b=a+b;a=b-a

Para el problema "Imprima el primer número de Fibonacci de más de 1000 dígitos":

a,b=1,1
i=1
while len(str(a))<=1000:
  i=i+1
  a,b=b,a+b

print i,len(str(a)),a

Lo sabemos

Y que la enésima potencia de esa matriz nos da:

Entonces podemos implementar una función que simplemente calcule la potencia de esa matriz a la potencia n-ésima -1.

como todos sabemos, el poder a ^ n es igual a

Entonces, al final, la función de Fibonacci sería O (n) ... nada realmente diferente a una implementación más fácil si no fuera por el hecho de que también lo sabemos x^n * x^n = x^2ny, por lo tanto, la evaluación x^nse puede hacer con la complejidad O (log n )

Aquí está mi implementación de Fibonacci usando lenguaje de programación rápido:

struct Mat {
    var m00: Int
    var m01: Int
    var m10: Int
    var m11: Int
}

func pow(m: Mat, n: Int) -> Mat {
    guard n > 1 else { return m }
    let temp = pow(m: m, n: n/2)

    var result = matMultiply(a: temp, b: temp)
    if n%2 != 0 {
        result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
    }
    return result
}

func matMultiply(a: Mat, b: Mat) -> Mat {
    let m00 = a.m00 * b.m00 + a.m01 * b.m10
    let m01 = a.m00 * b.m01 + a.m01 * b.m11
    let m10 = a.m10 * b.m00 + a.m11 * b.m10
    let m11 = a.m10 * b.m01 + a.m11 * b.m11

    return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}

func fibonacciFast(n: Int) -> Int {

    guard n > 0 else { return 0 }
    let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)

    return pow(m: m, n: n-1).m00
}

Esto tiene complejidad O (log n). Calculamos la potencia de Q con el exponente n-1 y luego tomamos el elemento m00 que es Fn + 1 que en el exponente de potencia n-1 es exactamente el enésimo número de Fibonacci que queríamos.

Una vez que tenga la función rápida de Fibonacci, puede iterar desde el número inicial y el número final para obtener la parte de la secuencia de Fibonacci que le interesa.

let sequence = (start...end).map(fibonacciFast)

por supuesto, primero realice algunas verificaciones al inicio y al final para asegurarse de que puedan formar un rango válido.

Sé que la pregunta tiene 8 años, pero me divertí respondiendo de todos modos. :)

Secuencia de Fibonacci es: 1, 1, 2, 3, 5, 8, ....

Es decir f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Mi implementación favorita (la más simple y, sin embargo, alcanza una velocidad de la luz en comparación con otras implementaciones) es esta:

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

Prueba

>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]

Sincronización

>>> %%time
>>> fibonacci(100**3)
CPU times: user 9.65 s, sys: 9.44 ms, total: 9.66 s
Wall time: 9.66 s

Editar: un ejemplo de visualización para esta implementación.

usar recursividad:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
x=input('which fibonnaci do you want?')
print fib(x)

Otra forma de hacerlo:

a,n=[0,1],10
map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2))

Asignar la lista a 'a', asignar un número entero a 'n' Map y reduce son 2 de las tres funciones más poderosas en python. Aquí el mapa se usa solo para iterar 'n-2' veces. un [-2:] obtendrá los dos últimos elementos de una matriz. a.append (x + y) agregará los dos últimos elementos y se agregará a la matriz

Todo esto parece un poco más complicado de lo que debe ser. Mi código es muy simple y rápido:

def fibonacci(x):

    List = []
    f = 1
    List.append(f)
    List.append(f) #because the fibonacci sequence has two 1's at first
    while f<=x:
        f = List[-1] + List[-2]   #says that f = the sum of the last two f's in the series
        List.append(f)
    else:
        List.remove(List[-1])  #because the code lists the fibonacci number one past x. Not necessary, but defines the code better
        for i in range(0, len(List)):
        print List[i]  #prints it in series form instead of list form. Also not necessary

De acuerdo ... después de estar cansado de referir todas las respuestas largas, ahora encuentre la forma más sencilla y dulce a continuación para implementar Fibonacci en Python. Puede mejorarlo de la manera que desee obteniendo un argumento u obteniendo la entrada del usuario ... o cambiando los límites de 10000. Según lo necesite ......

def fibonacci():
    start = 0 
    i = 1 
    lt = []
    lt.append(start)
    while start < 10000:
        start += i
        lt.append(start)
        i = sum(lt[-2:])
        lt.append(i)
    print "The Fibonaccii series: ", lt

Este enfoque también funciona bien. Encuentra los análisis de ejecución a continuación

In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop

Esta es una mejora a la respuesta de Matthew Henry:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print b
            a = b
            b = c

el código debe imprimir b en lugar de imprimir c

salida: 1,1,2,3,5 ....

Usando for loop e imprime solo el resultado

def fib(n:'upto n number')->int:
    if n==0:
        return 0
    elif n==1:
        return 1
    a=0
    b=1
    for i in range(0,n-1):
        b=a+b
        a=b-a
    return b

Resultado

>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>> 

Imprima el que listcontiene todos los números

def fib(n:'upto n number')->int:
    l=[0,1]
    if n==0:
        return l[0]
    elif n==1:
        return l
    a=0
    b=1
    for i in range(0,n-1):
        b=a+b
        a=b-a
        l.append(b)
    return l

Resultado

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

import time
start_time = time.time()



#recursive solution
def fib(x, y, upperLimit):
    return [x] + fib(y, (x+y), upperLimit) if x < upperLimit else [x]

#To test :

print(fib(0,1,40000000000000))
print("run time: " + str(time.time() - start_time))

Resultados

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368 13, en El

tiempo de ejecución: 0.04298138618469238

¡Hay un método muy fácil para darse cuenta de eso!

puede ejecutar este código en línea libremente utilizando http://www.learnpython.org/

# Set the variable brian on line 3!

def fib(n):
"""This is documentation string for function. It'll be available by fib.__doc__()
Return a list containing the Fibonacci series up to n."""
result = []
a = 0
b = 1
while a < n:
    result.append(a)  # 0 1 1 2 3 5  8  (13) break
    tmp_var = b       # 1 1 2 3 5 8  13
    b = a + b         # 1 2 3 5 8 13 21
    a = tmp_var       # 1 1 2 3 5 8  13
    # print(a)
return result

print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]

Se puede hacer de la siguiente manera.

n = 0

números = [0]

para i en rango (0,11):
    imprimir n,
    números.append (n)
    prev = números [-2]
    si n == 0:
        n = 1
    más:
        n = n + anterior

Solo por diversión, en Python 3.8+ puede usar una expresión de asignación (también conocido como el operador de morsa) en una comprensión de la lista, por ejemplo:

>>> a, b = 0, 1
>>> [a, b] + [b := a + (a := b) for _ in range(8)]  # first 10 Fibonacci numbers
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Una expresión de asignación le permite asignar un valor a una variable y devolverlo en la misma expresión. Por lo tanto, la expresión

b := a + (a := b)

es equivalente a ejecutar

a, b = b, a + b

y devolviendo el valor de b.

A los 15 minutos de un tutorial que usé cuando aprendí Python, le pidió al lector que escribiera un programa que calcule una secuencia de Fibonacci a partir de 3 números de entrada (primer número de Fibonacci, segundo número y número en el que detener la secuencia). El tutorial solo había cubierto variables, if / thens, y bucles hasta ese punto. Aún no hay funciones. Se me ocurrió el siguiente código:

sum = 0
endingnumber = 1                

print "\n.:Fibonacci sequence:.\n"

firstnumber = input("Enter the first number: ")
secondnumber = input("Enter the second number: ")
endingnumber = input("Enter the number to stop at: ")

if secondnumber < firstnumber:

    print "\nSecond number must be bigger than the first number!!!\n"

else:

while sum <= endingnumber:

    print firstnumber

    if secondnumber > endingnumber:

        break

    else:

        print secondnumber
        sum = firstnumber + secondnumber
        firstnumber = sum
        secondnumber = secondnumber + sum

Como puede ver, es realmente ineficiente, pero sí funciona.

def fib():
    a,b = 1,1
    num=eval(input("Please input what Fib number you want to be calculated: "))
    num_int=int(num-2)
    for i in range (num_int):
        a,b=b,a+b
    print(b)

Simplemente revisando http://projecteuler.net/problem=2 esta fue mi opinión al respecto

# Even Fibonacci numbers
# Problem 2

def get_fibonacci(size):
    numbers = [1,2]
    while size > len(numbers):
        next_fibonacci = numbers[-1]+numbers[-2]
        numbers.append(next_fibonacci)

    print numbers

get_fibonacci(20)

def fib(x, y, n):
    if n < 1: 
        return x, y, n
    else: 
        return fib(y, x + y, n - 1)

print fib(0, 1, 4)
(3, 5, 0)

#
def fib(x, y, n):
    if n > 1:
        for item in fib(y, x + y, n - 1):
            yield item
    yield x, y, n

f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55

Tal vez esto ayude

def fibo(n):
    result = []
    a, b = 0, 1
    while b < n:
            result.append(b)
            a, b = b, b + a
    return result

basado en la secuencia clásica de Fibonacci y solo por el bien de una línea

si solo necesita el número del índice, puede usar la reducción (incluso si la reducción no es la más adecuada para esto, puede ser un buen ejercicio)

def fibonacci(index):
    return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1]

y para obtener la matriz completa simplemente elimine o (r.pop (0) y 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])

¿Que tal este? Supongo que no es tan elegante como las otras sugerencias porque exige la especificación inicial del resultado anterior para producir el resultado esperado, pero creo que es una opción muy legible, es decir, todo lo que hace es proporcionar el resultado y el resultado anterior para La recursividad.

#count the number of recursions
num_rec = 0

def fibonacci(num, prev, num_rec, cycles):

    num_rec = num_rec + 1

    if num == 0 and prev == 0:
        result  = 0;
        num = 1;
    else:
        result = num + prev

    print(result)

    if num_rec == cycles:
        print("done")
    else:
        fibonacci(result, num, num_rec, cycles)

#Run the fibonacci function 10 times
fibonacci(0, 0, num_rec, 10)

Aquí está la salida:

0
1
1
2
3
5
8
13
21
34
done

Básicamente traducido de Ruby:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print c
            a = b
            b = c

...

def fib(lowerbound, upperbound):
    x = 0
    y = 1
    while x <= upperbound:
        if (x >= lowerbound):
            yield x
        x, y = y, x + y

startNumber = 10
endNumber = 100
for fib_sequence in fib(startNumber, endNumber):
    print "And the next number is... %d!" % fib_sequence

Una explicación más detallada de cómo funciona Memoization para la secuencia de Fibonacci.

# Fibonacci sequence Memoization

fib_cache = {0:0, 1:1}

def fibonacci(n):
    if n < 0:
        return -1
    if fib_cache.has_key(n):
        print "Fibonacci sequence for %d = %d cached" % (n, fib_cache[n])
        return fib_cache[n]
    else:
        fib_cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return fib_cache[n]

if __name__ == "__main__":
    print fibonacci(6)
    print fib_cache
    # fibonacci(7) reuses fibonacci(6) and fibonacci(5)
    print fibonacci(7)
    print fib_cache

Estaba tratando de evitar una función recursiva para resolver este problema, así que tomé un enfoque iterativo. Originalmente estaba haciendo una función recursiva memorable, pero seguí alcanzando la profundidad recursiva máxima. También tenía objetivos estrictos de memoria, por lo que me verás manteniendo la matriz lo más pequeña posible durante el proceso de bucle, manteniendo solo 2-3 valores en la matriz en cualquier momento.

def fib(n):
    fibs = [1, 1] # my starting array
    for f in range(2, n):
        fibs.append(fibs[-1] + fibs[-2]) # appending the new fib number
        del fibs[0] # removing the oldest number
    return fibs[-1] # returning the newest fib

print(fib(6000000))

Obtener el número 6 millones de Fibonacci toma alrededor de 282 segundos en mi máquina, mientras que el 600K Fibonacci toma solo 2.8 segundos. No pude obtener números de Fibonacci tan grandes con una función recursiva, incluso una memorable.