Числа Фибоначчи

Складывай два предыдущих числа — и получишь последовательность, спрятанную в шишках, цветах и спиралях.

Числа Фибоначчи — последовательность $0, 1, 1, 2, 3, 5, 8, 13, \dots$, где каждое число равно сумме двух предыдущих.

В 1202 году итальянец Леонардо Пизанский, известный как Фибоначчи, поставил задачу о кроликах: пара кроликов каждый месяц даёт новую пару, которая сама начинает размножаться со второго месяца. Сколько пар будет через $n$ месяцев? Ответ — последовательность, носящая его имя.

Рекуррентное определение

Формально последовательность задаётся правилом

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \;\; (n \ge 2).$$

Каждый следующий член — сумма двух предыдущих. Простота правила обманчива: из неё вырастает невероятно богатая математика. Числа Фибоначчи появляются в количестве лепестков у цветов (3 у лилии, 5 у лютика, 8 у дельфиниума), в спиралях подсолнуха и сосновой шишки, в родословной пчёл.

Считаем числа Фибоначчи

def fibonacci(n):
    a, b = 0, 1
    seq = []
    for _ in range(n):
        seq.append(a)
        a, b = b, a + b
    return seq

print("Первые 16 чисел:", fibonacci(16))
print("F(30) =", fibonacci(31)[-1])

Вывод:

Первые 16 чисел: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
F(30) = 832040

Как работает под капотом

В коде мы храним лишь два последних значения $a$ и $b$ и за один шаг превращаем их в $(b, a+b)$ — это итеративный способ, работающий за линейное время и почти без памяти. Наивная рекурсия $F(n) = F(n-1) + F(n-2)$ «в лоб» работает экспоненциально долго: она пересчитывает одни и те же значения много раз. Поэтому для Фибоначчи всегда выбирают итерацию или мемоизацию. У последовательности есть и красивые тождества, например $F_1 + F_2 + \dots + F_n = F_{n+2} - 1$ — сумма первых чисел снова почти Фибоначчи.

Частые ошибки

Путаница с индексацией: одни авторы начинают с $F_1 = 1, F_2 = 1$, другие — с $F_0 = 0$. Мы используем второй вариант, и его же требует формула Бине из следующего урока. Вторая ловушка — наивная рекурсия: для $n = 50$ она «зависнет», делая миллиарды повторных вызовов. Третья — забывать про $F_0 = 0$: без него ломаются многие формулы.

Итог

$F_n = F_{n-1} + F_{n-2}$, начиная с $F_0 = 0, F_1 = 1$.
Итеративный счёт хранит два значения и работает за линейное время.
Наивная рекурсия экспоненциальна — её избегают.
Числа Фибоначчи всплывают в биологии и геометрии.