Стек вызовов

В прошлом уроке комбайн factorial считал факториал цепочкой: каждый комбайн получал своё число, передавал работу соседу и ждал ответа. Пока комбайн ждёт, его число лежит у него внутри, и соседи его не трогают.

Давайте ещё раз посмотрим на эту функцию:

func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}

print(factorial(5)) // 120

Когда дело доходит до factorial(0), не завершён ни один из шести вызовов: factorial(5) ждёт результата factorial(4), тот ждёт factorial(3), и так далее. Параметр у них один и тот же, n, а значений шесть, от 5 до 0. Где программа держит все эти n и почему они не путаются?

Своя коробка у каждого вызова

Каждый вызов получает собственную коробку с параметрами и переменными. В коробке вызова factorial(5) лежит n, равное 5, а в коробке factorial(4) — своё n, равное 4. Одно имя, но шесть разных коробок.

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

Стопка коробок

Пока вызов не завершён, его коробка хранится в памяти. Эту область памяти называют стеком вызовов: новый вызов кладёт коробку сверху, а завершённый снимает верхнюю. Слово «стек» и значит «стопка»: как в стопке тарелок, класть и снимать можно только сверху.

Работает всегда тот вызов, чья коробка лежит сверху, а те, что ниже, ждут.

Нажимайте «Следующий шаг» и следите за столбиком коробок: он растёт до factorial(0), а потом коробки снимаются сверху. Чтобы столбик поместился на экране, здесь считается factorial(3).

Главное, что видно в виджете: у всех коробок одно имя n, но значения разные, и ни один вызов не трогает n другого.

Переполнение стека

Этот вопрос часто задают на собеседовании: что будет, если рекурсия не остановится? Ответ из трёх частей:

• каждый незавершённый вызов держит свою коробку в стеке вызовов;
• память для стека ограничена, и бесконечная рекурсия её исчерпывает — это называют переполнением стека;
• программа аварийно завершается.

Цикл вместо рекурсии

Тот же факториал можно посчитать циклом:

func factorialLoop(_ n: Int) -> Int {
    var result = 1
    for i in stride(from: 2, through: n, by: 1) {
        result *= i
    }
    return result
}

print(factorialLoop(5)) // 120

Цикл не делает новых вызовов: переменная result меняется на месте, и стек не растёт. Числа здесь перебирает stride, а не диапазон 2...n: при n меньше 2 такой диапазон завершил бы программу аварийно. А ряд stride в этом случае пуст, и функция возвращает 1.

Рекурсия повторяет определение слово в слово, а цикл расходует меньше памяти. Когда вызовов могут быть десятки тысяч и больше, выбирают цикл.

Частая ошибка

Рекурсивную функцию вызвали с аргументом, от которого базовый случай недостижим:

print(factorial(-1)) // ✗

Программа компилируется, но при запуске аварийно завершается. n становится -2, -3 и дальше, до нуля не доходит, и коробки копятся, пока память стека не кончится. Строки Fatal error здесь нет: программа останавливается из-за ошибки доступа к памяти.

Функцию совсем без базового случая компилятор замечает сам и предупреждает. А недостижимый базовый случай он не видит. Пусть базовый случай ловит каждое значение, на котором рекурсия должна остановиться: с условием n <= 0 вместо n == 0 вызов factorial(-1) вернёт 1, а не завершит программу аварийно.

Главное

• У каждого вызова своя коробка с параметрами, поэтому вызовы одной функции не путают свои n.
• Коробки лежат в стеке вызовов: новый вызов кладёт свою сверху, а завершённый снимает верхнюю.
• Память стека ограничена: если базовый случай недостижим, как у factorial(-1), стек переполняется, и программа аварийно завершается.
• Цикл не делает новых вызовов, и стек не растёт, поэтому при десятках тысяч повторений выбирают цикл.