Первоначально я неправильно написал программу. Вместо того, чтобы возвращать числа Фибоначчи между диапазоном (т.е. startNumber 1, endNumber 20 должны = только числа между 1 и 20), я написал для программы, чтобы отображать все числа Фибоначчи между диапазоном (например, startNumber 1, endNumber 20 отображает = Первые 20 чисел Фибоначчи). Я думал, что у меня есть надежный код. Я тоже не понимаю, почему это происходит.

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))

Кто-то указал в моей части II (которая была закрыта как дубликат - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ), что я необходимо передать startNumber и endNumber через генератор, используя цикл while. Может кто-нибудь указать мне, как это сделать? Любая помощь приветствуется.

Я обучающийся программист, и я наткнулся на небольшую путаницу. Меня просят написать программу, которая будет вычислять и отображать последовательность Фибоначчи по введенному пользователем начальному и конечному номерам (то есть startNumber = 20 endNumber = 100, и она будет отображать только числа между этим диапазоном). Уловка состоит в том, чтобы использовать его включительно (что я не знаю, как это сделать в Python? - Я предполагаю, что это означает использование включающего диапазона?).

Пока что у меня нет фактического кодирования, а скорее:

• Запишите формулу последовательности Фибоначчи до бесконечности
• Отображать startNumber в endNumber только из последовательности Фибоначчи.

Я не знаю, с чего начать, и прошу поделиться идеями или понять, как это написать. Я также пытался написать форум о последовательности Фибоначчи, но и в этом заблудился.

Есть много информации о последовательности Фибоначчи в Википедии и на вольфраме . Намного больше, чем вам может понадобиться. В любом случае полезно научиться использовать эти ресурсы, чтобы найти (если возможно, быстро) то, что вам нужно.

Запишите формулу последовательности Фибоначчи до бесконечности

В математике это дается в рекурсивной форме:

В программировании бесконечности не существует. Вы можете использовать рекурсивную форму, переводя математическую форму прямо на ваш язык, например, в Python она становится:

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

Попробуйте на своем любимом языке и убедитесь, что эта форма требует много времени, поскольку n становится больше. Фактически, это время O (2 ⁿ ).

Зайдите на сайты, которые я связал с вами, и увидите это (на вольфраме ):

Это довольно легко реализовать и очень, очень быстро вычислить на Python:

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

Другой способ сделать это - следовать определению (из Википедии ):

Первое число в последовательности - 0, второе число - 1, и каждое последующее число равно сумме двух предыдущих чисел самой последовательности, что дает последовательность 0, 1, 1, 2, 3, 5, 8. , так далее.

Если ваш язык поддерживает итераторы, вы можете сделать что-то вроде:

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

Отображать startNumber в endNumber только из последовательности Фибоначчи.

Как только вы знаете, как генерировать числа Фибоначчи, вам просто нужно циклически перебирать числа и проверять, подтверждают ли они заданные условия.

Предположим, теперь вы написали af (n), который возвращает n-й член последовательности Фибоначчи (например, с sqrt (5))

На большинстве языков вы можете сделать что-то вроде:

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

В python я бы использовал форму итератора и выбрал:

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

Мой совет - научитесь читать то, что вам нужно. Project Euler (Google для этого) научит вас этому: P Удачи и получайте удовольствие!

Эффективный питонический генератор последовательности Фибоначчи

Я нашел этот вопрос, пытаясь получить самую короткую Pythonic-генерацию этой последовательности (позже я понял, что видел подобное в предложении по расширению Python ), и я не заметил, чтобы кто-то еще предлагал мое конкретное решение (хотя главный ответ приближается, но все же менее элегантно), так что вот оно, с комментариями, описывающими первую итерацию, потому что я думаю, что это может помочь читателям понять:

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)

и использование:

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

печатает:

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

(Для целей атрибуции я недавно заметил аналогичную реализацию в документации Python по модулям, даже с использованием переменных aи b, которые, как я припоминаю, видел перед написанием этого ответа. Но я думаю, что этот ответ демонстрирует лучшее использование языка.)

Рекурсивно определенная реализация

Интернет Энциклопедия целочисленных последовательностей определяет последовательность Фибоначчи рекурсивно

F (n) = F (n-1) + F (n-2) с F (0) = 0 и F (1) = 1

Кратко определить это рекурсивно в Python можно следующим образом:

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

Но это точное представление математического определения невероятно неэффективно для чисел, намного превышающих 30, потому что каждое вычисляемое число должно также вычисляться для каждого числа ниже него. Вы можете продемонстрировать, насколько он медленный, используя следующее:

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

Мемоизированная рекурсия для эффективности

Его можно запоминать для повышения скорости (в этом примере используется тот факт, что аргумент ключевого слова по умолчанию является одним и тем же объектом каждый раз при вызове функции, но обычно вы не будете использовать изменяемый аргумент по умолчанию именно по этой причине):

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

Вы обнаружите, что мемоизированная версия работает намного быстрее и быстро превысит вашу максимальную глубину рекурсии, прежде чем вы даже сможете подумать о том, чтобы встать для кофе. Вы можете визуально увидеть, насколько это быстрее, сделав следующее:

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

(Может показаться, что мы можем просто сделать следующее, но на самом деле это не позволяет нам воспользоваться кешем, потому что он вызывает себя до вызова 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

Рекурсивно определенный генератор:

Изучая Haskell, я наткнулся на эту реализацию в Haskell:

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

На данный момент я думаю, что ближе всего к этому в Python я могу подойти:

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

Это демонстрирует:

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

Однако он может доходить только до предела рекурсии. Обычно 1000, тогда как версия Haskell может доходить до сотен миллионов, хотя для этого используются все 8 ГБ памяти моего ноутбука:

> length $ take 100000000 fib 
100000000

Использование итератора для получения n-го числа Фибоначчи

Комментатор спрашивает:

Вопрос к функции Fib (), основанной на итераторе: что делать, если вы хотите получить n-е, например 10-е число fib?

В документации itertools есть рецепт для этого:

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)

и сейчас:

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

Почему бы просто не сделать следующее?

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

Идея последовательности Фибоначчи показана в следующем коде Python:

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

Это означает, что fib - это функция, которая может делать одно из трех. Он определяет fib (1) == 1, fib (0) == 0 и fib (n) как:

фиб (п-1) + фиб (п-2)

Где n - произвольное целое число. Это означает, что, например, fib (2) расширяется до следующей арифметики:

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

Мы можем вычислить fib (3) таким же образом с помощью арифметики, показанной ниже:

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

Здесь важно понимать, что fib (3) не может быть вычислен без вычисления fib (2), которое вычисляется, зная определения fib (1) и fib (0). Сам вызов функции, такой как функция Фибоначчи, называется рекурсией, и это важная тема в программировании.

Это звучит как домашнее задание, поэтому я не буду делать за вас начальную / конечную часть. Python - удивительно выразительный язык для этого, так что это должно иметь смысл, если вы разбираетесь в математике, и, надеюсь, научит вас рекурсии. Удачи!

Изменить: одна из потенциальных критических замечаний по поводу моего кода заключается в том, что он не использует супер-удобную функцию Python yield, что делает функцию fib (n) намного короче. Однако мой пример немного более общий, поскольку не многие языки, кроме Python, действительно имеют yield.

Временная сложность:

Функция кэширования сокращает обычный способ вычисления рядов Фибоначчи с O (2 ^ n) до O (n) за счет исключения повторов в рекурсивном дереве рядов Фибоначчи:

Код:

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()

Это довольно эффективно, используя O (log n) основных арифметических операций.

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

Здесь используется O (1) базовых арифметических операций, но размер промежуточных результатов велик и поэтому неэффективен.

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

Этот вычисляет X ^ n в кольце многочленов Z [X] / (X ^ 2 - X - 1), используя возведение в степень возведением в квадрат. Результатом этого вычисления является полином Fib (n) X + Fib (n-1), из которого можно прочитать n-е число Фибоначчи.

Опять же, это использует O (log n) арифметических операций и очень эффективно.

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]

Канонический код Python для печати последовательности Фибоначчи:

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

Для задачи «Выведите первое число Фибоначчи длиной более 1000 цифр»:

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

Мы знаем это

И что n-я степень этой матрицы дает нам:

Таким образом, мы можем реализовать функцию, которая просто вычисляет степень этой матрицы в степени n -1.

как все мы знаем, мощность a ^ n равна

Итак, в конце функция фибоначчи была бы O (n) ... ничем не отличалось бы от более простой реализации, если бы не тот факт, что мы также это знаем, x^n * x^n = x^2nи x^nпоэтому оценка может быть выполнена со сложностью O (log n )

Вот моя реализация Фибоначчи с использованием быстрого языка программирования:

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
}

Это имеет сложность O (log n). Мы вычисляем степень Q с показателем n-1, а затем берем элемент m00, который представляет собой Fn + 1, который при показателе степени n-1 является в точности n-м числом Фибоначчи, которое мы хотели.

Когда у вас есть быстрая функция Фибоначчи, вы можете выполнять итерацию от начального числа до конечного числа, чтобы получить интересующую вас часть последовательности Фибоначчи.

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

конечно, сначала выполните некоторую проверку начала и конца, чтобы убедиться, что они могут сформировать допустимый диапазон.

Я знаю, что этому вопросу 8 лет, но мне все равно было весело отвечать. :)

Последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, ....

То есть f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Моя любимая реализация (самая простая и, тем не менее, обеспечивает небольшую скорость по сравнению с другими реализациями):

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

Контрольная работа

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

Время

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

Изменить: пример визуализации для этой реализации.

использовать рекурсию:

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)

Другой способ сделать это:

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

Назначение list для 'a', присвоение целого числа 'n' Map и сокращение - это 2 из трех самых мощных функций в python. Здесь карта используется только для повторения "n-2" раз. a [-2:] получит два последних элемента массива. a.append (x + y) добавит последние два элемента и добавит в массив

Все это выглядит немного сложнее, чем должно быть. Мой код очень простой и быстрый:

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

Хорошо ... после того, как вы устали ссылаться на все длинные ответы, теперь найдите ниже сортированный и приятный, довольно простой способ реализации Фибоначчи в python. Вы можете улучшить его так, как вы хотите, получив аргумент или введя данные пользователя… или изменив пределы с 10000. По мере необходимости ……

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

Этот подход тоже работает хорошо. Найдите аналитику пробега ниже

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

это улучшение ответа Мэтью Генри:

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

код должен печатать b вместо c

выход: 1,1,2,3,5 ....

Использование цикла for и печать только результата

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

Результат

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

Выведите listсодержащий все числа

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

Результат

>>> 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))

Полученные результаты

[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 , 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 43334117167373, 701401107373 , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 405273953700920, 2504730781961, 405277639537003107781961, 40527763953700351

время работы: 0.04298138618469238

есть очень простой способ понять это!

вы можете бесплатно запустить этот код в Интернете, используя 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]

Сделать это можно следующим образом.

п = 0

числа = [0]

для i в диапазоне (0,11):
    напечатать n,
    numbers.append (n)
    пред = числа [-2]
    если n == 0:
        п = 1
    еще:
        n = n + пред.

Если вы поклонник рекурсии, вы можете легко кэшировать результаты с помощью lru_cacheдекоратора (наименее использованный декоратор кеша)

from functools import lru_cache


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

Если вам нужно кэшировать более 128 значений, вы можете передать их maxsizeв качестве аргумента lru_cache(например, lru_cache(maxsize=500)если вы установите maxsize=Noneкеш может неограниченно расти.

Для развлечения в Python 3.8+ вы можете использовать выражение присваивания (также известное как оператор моржа) в понимании списка, например:

>>> 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]

Выражение присваивания позволяет присвоить значение переменной и вернуть его в том же выражении. Следовательно, выражение

b := a + (a := b)

эквивалентно выполнению

a, b = b, a + b

и возвращает значение b.

15 минут в учебнике, который я использовал при изучении Python, он попросил читателя написать программу, которая будет вычислять последовательность Фибоначчи из 3 входных чисел (первое число Фибоначчи, второе число и число, на котором следует остановить последовательность). В руководстве были рассмотрены только переменные, if / thens и циклы до этого момента. Функций пока нет. Я придумал следующий код:

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

Как видите, это действительно неэффективно, но ДЕЙСТВИТЕЛЬНО работает.

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)

Просто прохожу http://projecteuler.net/problem=2, это было мое мнение

# 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

Может это поможет

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

на основе классической последовательности Фибоначчи и просто ради однострочности

если вам просто нужно номер индекса, вы можете использовать уменьшить (даже если уменьшить это не лучше всего подходит для этого он может быть хорошим упражнением)

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]

и чтобы получить полный массив, просто удалите или (r.pop (0) и 0)

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

Как насчет этого? Я предполагаю, что это не так необычно, как другие предложения, потому что для получения ожидаемого результата требуется начальная спецификация предыдущего результата, но я считаю, что это очень удобочитаемый вариант, то есть все, что он делает, это предоставляет результат и предыдущий результат для рекурсия.

#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)

Вот результат:

0
1
1
2
3
5
8
13
21
34
done

В основном переведено с 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

Более подробное объяснение того, как работает мемоизация для последовательности Фибоначчи.

# 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