Учебник по информатике и математике
Темы
C++
Основы языка
Факториал и числа Фибоначчи: рекурсия и цикл
Оглавление:
Класс собирается на общее фото, и фотограф хочет поставить в первый ряд пятерых. Сколькими способами их можно расставить? На первое место — любого из пяти, на второе — любого из оставшихся четырех, и так далее: $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ вариантов. Для десяти человек вариантов уже 3 628 800.
Такое произведение называется факториалом. Факториал и числа Фибоначчи — классические примеры рекурсии: на них видно, когда она удобна, когда опасно медленная и как это исправить.
Факториал
Факториал числа $n$ — произведение всех натуральных чисел от 1 до $n$. Его обозначают восклицательным знаком: $n! = 1 \cdot 2 \cdot \ldots \cdot n$. По договоренности $0! = 1$.
Заметь, что $5! = 5 \cdot 4!$, а $4! = 4 \cdot 3!$. В общем виде $n! = n \cdot (n - 1)!$ — это готовый шаг рекурсии, а базовый случай — $0! = 1! = 1$. Запишем два решения, рекурсивное и через цикл:
def factorial_rec(n):
if n <= 1: # базовый случай: 0! = 1! = 1
return 1
return n * factorial_rec(n - 1) # шаг: n! = n * (n - 1)!
def factorial_loop(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
print(factorial_rec(5)) # 120
print(factorial_loop(10)) # 3628800
Оба решения работают за $O(n)$: нужно около $n$ умножений. Но рекурсивная версия держит в стеке $n$ ожидающих вызовов, и factorial_rec(1000) упадет с RecursionError — предел глубины в Python около 1000. А factorial_loop(1000) посчитает число из 2568 цифр — целые числа в Python не переполняются.
Числа Фибоначчи
Последовательность Фибоначчи начинается с 0 и 1, а каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
Пример из жизни: ты поднимаешься по лестнице, шагая через одну или две ступеньки. Сколькими способами можно подняться на $n$ ступенек? На последнюю ты попадаешь либо с предпоследней, либо со ступеньки ниже нее. Значит, способов столько, сколько для $n - 1$ и $n - 2$ ступенек вместе — это правило Фибоначчи. Для 4 ступенек их $F_5 = 5$.
Определение переводится в код почти дословно:
def fib(n):
if n < 2: # F(0) = 0, F(1) = 1
return n
return fib(n - 1) + fib(n - 2)
print(fib(10)) # 55
print(fib(30)) # 832040
Почему наивная рекурсия медленная
Функция много раз считает одно и то же: fib(5) вызывает fib(4) и fib(3), но fib(4) снова вызывает fib(3), и так на каждом шаге. Посмотри, как растет число вызовов:
| $n$ | Сколько раз вызовется fib |
|---|---|
| 10 | 177 |
| 20 | 21 891 |
| 30 | 2 692 537 |
| 40 | 331 160 281 |
Когда $n$ растет на единицу, вызовов становится примерно в 1,6 раза больше. Такой рост называют экспоненциальным, и сложность наивного Фибоначчи грубо оценивают как $O(2^n)$. Поэтому fib(30) считается за доли секунды, fib(40) на обычном ноутбуке занимает секунды, а то и десятки секунд, а fib(50) — уже минуты.
Цикл: быстро и без стека
Сам ты считал бы иначе: слева направо, помня только два последних числа. Так же работает цикл:
def fib_loop(n):
a, b = 0, 1 # F(0) и F(1)
for _ in range(n):
a, b = b, a + b # сдвигаемся на одно число вперед
return a
print(fib_loop(10)) # 55
print(fib_loop(100)) # 354224848179261915075
Подчеркивание _ — имя для переменной, значение которой не нужно. Цикл делает $n$ шагов, сложность $O(n)$. Сотое число Фибоначчи считается мгновенно, а наивной рекурсии на него понадобилось бы больше ста тысяч лет.
Мемоизация: рекурсия с памятью
Рекурсию можно оставить, если запоминать найденные ответы. Этот прием называется мемоизацией (от английского memo — «заметка»). В Python для него есть декоратор lru_cache из модуля functools:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(100)) # 354224848179261915075
Строка с @ над функцией — декоратор: он «оборачивает» функцию и запоминает результат для каждого аргумента. Когда fib(3) понадобится второй раз, ответ возьмется из памяти. Теперь каждое число от fib(0) до fib(100) считается один раз, и время падает с $O(2^n)$ до $O(n)$. maxsize=None снимает ограничение на число запомненных ответов.
Совет: Мемоизация не отменяет предел глубины:
fib(5000)с пустым кешем все равно упадет сRecursionError. Для больших $n$ надежнее цикл. А факториал в настоящих программах вручную не пишут: есть готовая функцияmath.factorial(n).
Частые ошибки
Частая ошибка: Если у Фибоначчи оставить один базовый случай
if n == 0: return 0, вызовfib(1)уйдет вfib(0)иfib(-1). Отрицательные числа никогда не дойдут до нуля, и программа упадет сRecursionError. Проверкаn < 2закрывает оба базовых случая.
result = 0в факториале через цикл: произведение всегда будет нулем, начинать надо с 1.range(2, n)вместоrange(2, n + 1): последнее число $n$ не войдет, и получится $(n - 1)!$.
Проверь себя
Сколько всего раз вызовется функция fib (наивная рекурсия) при вычислении fib(4), считая и первый вызов?
Сколькими способами можно подняться по лестнице из 6 ступенек, если шагать на одну или на две ступеньки?
Соедини строку кода и ее роль.
@lru_cache(maxsize=None)
Базовый случай для Фибоначчи
if n < 2: return n
Запоминает результаты вызовов
a, b = b, a + b
Шаг рекурсии для факториала
return n * factorial_rec(n - 1)
Шаг цикла для Фибоначчи