Коротко и по делу.
Почему рекурсивный вариант медленнее:
- Наивный рекурсивный алгоритм повторно решает одни и те же подзадачи. Вызовы удовлетворяют рекурренции
$$T(n)=T(n-1)+T(n-2)+O(1),$$ что даёт экспоненциальную сложность времени
$$T(n)=\Theta ({\phi }^n),$$ где $\phi =\frac{1+\sqrt{5}}{2}\approx \mathrm{1.618.}$ - Кроме того каждое рекурсивное вызов-возврат — накладные расходы на вызов функции и стек. По памяти наивная рекурсия использует стек глубиной $O(n)$.
- Итеративный расчёт выполняет $n$ шагов и требует $O(1)$ дополнительной памяти, т.е. время $O(n)$, память $O(1)$.
Когда уместна мемоизация:
- Когда функция чиста (без побочных эффектов) и имеются перекрывающиеся подзадачи (как в Fibonacci). Тогда кеширование результатов превращает экспоненту в линейную сложность:
время $O(n)$, память $O(n)$.
- Простейшая реализация в Python:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_recursive(n):
if n < 2:
return n
return fib_recursive(n-1) + fib_recursive(n-2)
Риски и что учитывать при оптимизациях:
- Глубина рекурсии: Python имеет ограничение стека (по умолчанию около $1000$); при больших $n$ возможен RecursionError. Поднимание лимита рискованно.
- Память кеша: неограниченный кеш может привести к утечке памяти при множественных различающихся вызовах; используйте ограниченный кеш (maxsize) или очищайте его при необходимости.
- Побочные эффекты и изменяемые/нехешируемые аргументы: мемоизация безопасна только для детерминированных функций с хешируемыми аргументами; кеширование подавит побочные эффекты.
- Накладные расходы: кеш lookup и блокировки (в lru_cache) добавляют константные накладные расходы, так что для малых $n$ итератив может быть быстрее.
- Многопоточность: возможны блокировки/контенция в общих кешах.
- Отсутствие оптимизации хвостовой рекурсии в Python: даже трансформированные рекурсивные формы не будут оптимизированы в стек.
Если требуется очень большие $n$: лучше использовать итеративный подход или алгоритмы со сложностью $O(\log n)$ (быстрое удвоение / матричное возведение в степень).