Последовательность Фибоначчи

Эта последовательность известна с древних времен. Её следы встречаются в музыке, искусстве и математике. Программирование тоже обратило на неё внимание.

Существует множество последовательностей, похожих на Фибоначчи, и их определения могут различаться. Мы будем придерживаться такого:

Последовательность Фибоначчи — это целочисленный ряд чисел.

0,1,1,2,3,5,...

Первые два элемента — 0 и 1. Каждый следующий элемент — это сумма двух предыдущих. Нумерация элементов начинается с нуля.

Функция Фибоначчи принимает порядковый номер и возвращает значение элемента последовательности Фибоначчи под этим номером.

fib(0)=0
fib(1)=1
fib(2)=1
...
fib(5)=5
fib(6)=8
...

Определение можно дать и в строгом математическом виде:

Рассмотрим простое решение этой задачи.

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

# Пример использования
for i in range(10):
    print(f"fib({i}) = {fib_iter(i)}")

Как это работает:

• a хранит текущее значение,
• b — следующее.
• На каждой итерации они меняются местами, и мы вычисляем новое число.

Сложность: O(n) — работает быстро даже для больших n.

Рекурсивное решение

Рекурсия — это вызов функции самой себя.

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

# Пример
for i in range(10):
    print(f"fib({i}) = {fib_rec(i)}")

Особенности:

• Очень красиво и похоже на математическое определение.
• Есть точка выхода: если n < 2, мы сразу возвращаем n.
• Минус — работает медленно при больших n, потому что одни и те же значения вычисляются много раз.

Сложность: примерно O(2^n) — экспоненциально.

В любой рекурсивной функции есть точка выхода — момент, когда ответ очевиден. В нашем случае это ситуация, когда n меньше 2. Тогда мы просто возвращаем n. Если n больше или равно 2, нужно сначала вызвать функцию fib() для n−1, потом для n−2, а затем сложить их результаты.

Рекурсия с мемоизацией (кэшированием)

Чтобы не вычислять одно и то же значение несколько раз, можно хранить уже найденные результаты.

cache = {}

def fib_memo(n):
    if n < 2:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]

# Пример
for i in range(10):
    print(f"fib({i}) = {fib_memo(i)}")

Как это работает:

• cache — словарь, в котором ключом является n, а значением — fib(n).
• Если число уже вычислено, просто возвращаем его из памяти.
• Это резко ускоряет работу.

Сложность: O(n) — почти так же быстро, как итеративный метод.

Вывод

• Для маленьких значений n можно использовать любой способ.
• Для больших значений лучше применять итерацию или рекурсию с мемоизацией.
• Понимание этих трёх подходов полезно, чтобы лучше понимать и рекурсию, и оптимизацию алгоритмов.