Рекурсия
Введено| English | Значение |
|---|---|
| recursive/rɪˈkɜːsɪv/ | рекурсивный |
| base case/beɪs keɪs/ | базовый случай |
| recursive case/rɪˈkɜːsɪv keɪs/ | рекурсивный случай |
| call stack/kɔːl stæk/ | стек вызовов |
| stack frame/stæk freɪm/ | кадр стека |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | переполнение стека |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | мемоизация |
Определение, содержащее само себя
- Как определить, кто такой предок? Ваш родитель — ваш предок. Предок вашего родителя — тоже ваш предок. Эти два предложения задают бесконечную цепочку, при этом второе предложение использует слово, которое оно же и определяет.
- Это не круговой логический оборот, потому что первое предложение задает точку остановки для этой цепочки. Без этого определения раскручивалось бы навсегда.
- Программы можно писать одинаково, но для задач, имеющих структуру такой цепочки, рекурсивное решение значительно короче, чем цикл.
- Этот урок посвящен базовому случаю и рекурсивному случаю, тому, как прослеживается вызов рекурсии, и тому, что происходит внутри стека вызовов.
Два случая
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- Базовый случай — это упрощенная версия задачи, достаточно простая для прямого ответа без дальнейших вызовов. Именно он останавливает рекурсию.
- Рекурсивный случай снова вызывает функцию с меньшим входным значением, приближаясь к базовому случаю.
- Оба случая обязательны. Рекурсия без базового случая никогда не остановится; рекурсия, чей входной параметр не уменьшается, никогда не достигнет базового случая.
Every recursive algorithm must have a base case because:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Recursion is a natural fit for self-similar problems (trees, divide-and-conquer), but each call adds a stack frame — so without a base case it overflows the stack.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself.
What must a recursive routine have to terminate? Select все that apply.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
A base case alone is not enough: if the input never shrinks, the base case is never reached and frames pile up until the stack overflows.
Разбор примера: проследите рекурсию
- Проследите
Factorial(4). - Раскрутка (накопление) вызовов:
Factorial(4)требует4 * Factorial(3), который требует3 * Factorial(2), который требует2 * Factorial(1). Ничего еще не перемножено; каждый вызов ожидает результата. - Базовый случай:
Factorial(1)возвращает 1, не вызывая ничего дальше. - Скрутка (возврат) значений: сначала возвращается
2 * 1 = 2, затем3 * 2 = 6, затем4 * 6 = 24. - Показывайте оба направления. Проследив только спуск или только возврат, вы потеряете половину баллов.
Recursion unwinds from the leaves up
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow.
What does Factorial(4) return?
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
4 × 3 × 2 × 1 = 24.
Что делает машина
- Каждый вызов требует собственной копии своих параметров и локальных переменных, поскольку
Factorial(3)иFactorial(2)— это разные вызовы с разными значениямиn. - Эти копии хранятся в кадре стека на стеке вызовов: по одному кадру на каждый активный вызов, содержащему параметры, локальные переменные и адрес возврата.
- Рамка push-ится при каждом вызове и pop-ится при возврате. Вот почему значения возвращаются в обратном порядке относительно порядка вызова: стек вызовов представляет собой стек, точно такой же ADT, что и в теме 10.
Put the events of evaluating Factorial(4) in order.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
Что может пойти не так
- Отсутствие базового случая или базового случая, который никогда не достигается: рекурсия никогда не останавливается, кадры накапливаются, и стек вызовов исчерпывает память. Это переполнение стека (stack overflow).
- Глубокая рекурсия: даже корректная рекурсия на миллион уровней требует миллион кадров, что может исчерпать память там, где цикл не потребил бы ничего.
- Дублирование работы: наивный рекурсивный Фибоначчи пересчитывает одни и те же значения экспоненциальное число раз. Исправьте это циклом или мемоизацией, сохраняя каждый результат при первом его вычислении.
Match each recursion term to what it means.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame.
A stack frame for a function call holds:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
Each call in progress keeps its parameters and locals in its own ____ on the call stack.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
Рекурсия или итерация
- Рекурсия подходит для самоподобных задач, где задача содержит меньшую копию самой себя: обход дерева, деление и властвование, такие как бинарный поиск и merge sort, и приведенная выше цепочка предков.
- Итерация подходит для всего остального и не требует дополнительной памяти для повторения.
- Любую рекурсивную задачу можно записать итеративно, и наоборот. Выбор зависит от того, какой подход яснее выражает суть задачи, в сравнении с затратами памяти на стек.
A recursive routine crashes with a stack overflow. Which explanation is correct?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
Разбор примера: назовите риски
- Студент пишет рекурсивную процедуру, и она падает с ошибкой переполнения стека. Назовите две возможные причины.
- Отсутствует базовый случай, либо базовый случай никогда не достигается, так как входной параметр не уменьшается с каждым вызовом, поэтому вызовы продолжаются бесконечно, а кадры накапливаются.
- Рекурсия корректна, но слишком глубока: каждый из очень многих вызовов хранит свой собственный кадр стека, и стек вызовов исчерпывает память до достижения базового случая.
- Обе причины связаны с накоплением кадров. Укажите, что именно накапливается и почему это не прекращается.
Потерянные баллы
- Для рекурсии нужны оба условия: базовый случай и входной параметр, который уменьшается. Упоминание только базового случая — это лишь половина условия.
- При прослеживании показывайте вызовы, накапливающиеся до базового случая, и значения, возвращающиеся обратно. Оба направления оцениваются баллами.
- У каждого вызова есть собственные параметры и локальные переменные в своем собственном кадре стека. Именно поэтому рекурсия требует памяти, которая не нужна итерации.
- Переполнение стека (stack overflow) — это нехватка памяти стека из-за слишком большого количества кадров, а не арифметическое переполнение.
Вы поняли
- рекурсивная процедура требует базового случая, решаемого напрямую, и рекурсивного случая, который вызывает саму себя с меньшим входным значением
- проследите её в обоих направлениях: вызовы накапливаются до базового случая, затем значения возвращаются назад
- у каждого вызова есть свой собственный кадр стека на стеке вызовов, добавляемый при вызове и удаляемый при возврате, именно поэтому рекурсия требует памяти
- риски: отсутствие достижимого базового случая приводит к бесконечной рекурсии и переполнению стека, глубокая рекурсия исчерпывает память, а повторяющиеся вычисления требуют цикла или мемоизации