Генератор чисел Фибоначчи

«Числа Фибоначчи или золотое сечение составляют основу разгадки окружающего мира, построения его формы и оптимального зрительного восприятия человеком, с помощью которых он может ощущать красоту и гармонию. Принцип определения размеров золотого сечения лежит в основе совершенства целого мира и его частей в своей структуре и функциях, его проявление можно видеть в природе, искусстве и технике.» — по материалам сайта school-science.ru.

Получение последовательности чисел Фибоначчи часто является учебной задачей при изучении языков программирования. Давайте рассмотрим принцип построения самой последовательности, который состоит в следующем: первые два числа равны 1, а каждое следующее является суммой двух предыдущих. Поняв идею, давайте напишем генератор чисел Фибоначчи на языке Python.

def gen_fib(n):
    n1, n2 = 1, 1
    for i in range(1, n + 1):
        if i < 3:
            yield 1
        else:
            yield n1 + n2
            n1, n2 = n2, n1 + n2

В качестве параметра функция получает требуемое количество чисел. Записываем начальные значения в переменные n1, n2 и запускаем цикл генерации. Как только встречается оператор yield, наша функция приостанавливает своё выполнение и возвращает очередное число Фибоначчи. Далее при очередном вызове выполнение начинается с оператора, следующего за yield. Чтобы вывести, например, в строку через пробел N чисел Фибоначчи, можно использовать следующий код:

N = int(input())

gen = gen_fib(N)
for j in range(1, N + 1):
    print(next(gen), end=' ')

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

def fib_rec(N, f=[]):
    if N == 0:
        return f
    if N == 1:
        return [1]
    if N == 2:
        return [1, 1]
    if N > 2:
        f = fib_rec(N - 1, f)
        f.append(f[-1] + f[-2])
        return f 

В функции первые 3 оператора if являются условиями выхода из рекурсии. В 4 операторе if формируются числа последовательности Фибоначчи с использованием рекурсивного вызова самой этой функции. Ранее созданные числа уже хранятся в списке, поэтому нам промежуточные переменные n1, n2 не нужны в этом варианте функции. Для получения списка из N чисел и вывода его на экран можно использовать следующий код:

N = int(input())
lst = fib_rec(N)
print(lst)

Для N=7 будет выведено:

[1, 1, 2, 3, 5, 8, 13]

Приведу ещё 1 вариант функции с применением декоратора, сохраняющего результаты предыдущих вычислений. Он позволяет ускорить получение значений при повторении одинаковых запросов. Внутри функции-декоратора создаём словарь вычисленных ранее значений и заносим в него результаты вычислений. Если число запрашивалось ранее, то возвращается значение для него из словаря. В противном случае производятся вычисления и результат заносим в словарь.

from functools import wraps
# Определение декоратора memoize  
def memoize(func):
    d = dict()
    @wraps(func)
    def decor(*args, **kwargs):
        nonlocal d
        if args[0] not in d:
            res = func(*args, **kwargs)
            d[args[0]] = res
        return d[args[0]]
    return decor     

@memoize
def fibonacci(n):
    """
    Возвращает n-ое число Фибоначчи
    """
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

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