Сколько стоит рекурсия и сколько она ест памяти

Рекурсия ничего не ускоряет и ничего не замедляет сама по себе. Стоимость задаётся тем, сколько вызовов она порождает и что делает каждый. Считать это надо до запуска - иначе легко написать программу, которая на входе из сорока элементов будет работать дольше, чем существует Солнечная система.

Как думаешь, во сколько раз это дороже

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

При n = 30 эта функция делает больше двух с половиной миллионов вызовов. При n = 40 - около трёхсот тридцати миллионов. Каждое увеличение n на единицу умножает работу примерно на 1,6.

Причина не в рекурсии, а в том, что дерево вызовов ветвится, а подзадачи повторяются: fib(28) считается заново в каждой ветке, где встретился.

Дерево вызовов

Работу рекурсии удобно считать по её дереву: узел - один вызов, потомки - вызовы, которые он делает. Нужны две величины.

Число узлов даёт время: сумма работы по всем вызовам. Если каждый вызов делает константную работу, время пропорционально числу узлов.

Глубина даёт память. Кадр вызова - это запись, которую машина заводит на каждый начатый вызов: в ней лежат аргументы, локальные переменные и адрес возврата. Кадры складываются в стопку, которую называют стеком вызовов, и во время работы в ней лежат все вызовы от корня до текущего узла, а не всё дерево целиком.

Считаем вместе: три рекурсии и их цена

Один вызов на уровень. summa(a, i) из прошлого урока вызывает себя один раз, глубина n, узлов n. Время n, память n - и вторая цифра неприятная: на списке из миллиона элементов рекурсия упрётся в предел глубины стека.

Два вызова, но каждый вдвое меньше. Сортировка слиянием делит массив пополам: на уровне k идёт 2^k вызовов размера n/2^k, работа на уровне n, уровней log₂ n. Итого n·log₂ n времени и log₂ n глубины. При n = 1 000 000 глубина около двадцати.

Два вызова размера n-1. Ханойские башни: узлов 2ⁿ - 1, глубина n. Время экспоненциальное, память линейная - и здесь это не дефект, а свойство задачи: ходов действительно 2ⁿ - 1.

Два вызова размера n-1 и n-2 с повторами. fib - узлов около 1,618ⁿ. Здесь экспонента уже дефект: тех же чисел можно достичь за n шагов, если не считать одно и то же дважды. К этому вернёмся в разделе про динамическое программирование.

Считаем вместе: глубина против ветвления

Пусть каждый вызов делает константную работу и порождает b вызовов размера n-1. Тогда узлов примерно bⁿ, глубина n.

• b = 1: время n, память n - обычный цикл, записанный рекурсией;
• b = 2: время 2ⁿ, память n - перебор подмножеств;
• b = 2, но размер делится пополам: время n, память log n - двоичный поиск, записанный рекурсией.

Отсюда видно, что вопрос «рекурсия или цикл» не про скорость. Скорость задаёт форма дерева. Рекурсия отличается только тем, что платит памятью за стек и избавляет от ручного хранения состояния.

Хвостовая рекурсия и её отсутствие в Python

Если рекурсивный вызов - последнее действие функции, кадр вызывающего больше не нужен, и компилятор мог бы переиспользовать его вместо создания нового. Такой приём называется оптимизацией хвостового вызова.

В Python его нет и не будет: разработчики языка отказались от него сознательно, чтобы сохранить полную трассу вызовов в отчёте об ошибке. Практическое следствие - предел глубины около тысячи вызовов, после чего программа падает. Поэтому рекурсию глубиной n в Python пишут только там, где n заведомо мало, а глубину log n - свободно.

Теперь сам

Функция обходит двоичное дерево из n узлов и возвращает его высоту:

def vysota(uzel):
    if uzel is None:
        return -1
    return 1 + max(vysota(uzel.levyj), vysota(uzel.pravyj))

Сколько вызовов она делает и какова глубина стека для дерева-цепочки из n узлов и для сбалансированного дерева из n узлов?