Дерево рекурсии
Посмотрите, как рекурсивная функция вызывает сама себя: каждый вызов раскрывается в дочерние, а результаты возвращаются снизу вверх. Видно, почему Фибоначчи «взрывается», а факториал — нет. Считается прямо в браузере.
вызовов: 15
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Готовим дерево…
Как читать дерево вызовов
Корень — первый вызов функции. Стрелки вниз — вложенные вызовы, которые она делает, пока не дойдёт до базового случая (условия выхода). Затем результаты возвращаются снизу вверх (подпись «→ значение»). У факториала и суммы каждый вызов делает один вложенный — дерево вытянуто в линию, глубина n. У Фибоначчи вызовов два, поэтому число вызовов растёт экспоненциально — отсюда видно, зачем нужна мемоизация. У Ханоя число ходов равно 2ⁿ−1.
