Рекурсия
| 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
- Базовый случай — это упрощенная версия задачи, достаточно простая для прямого ответа без дальнейших вызовов. Именно он останавливает рекурсию.
- Рекурсивный случай снова вызывает функцию с меньшим входным значением, приближаясь к базовому случаю.
- Оба случая обязательны. Рекурсия без базового случая никогда не остановится; рекурсия, чей входной параметр не уменьшается, никогда не достигнет базового случая.
Каждый рекурсивный алгоритм должен иметь базовый случай, потому что:
Базовый случай — это условие, завершающее цепочку вызовов; без него рекурсия будет работать вечно.
Рекурсия естественно подходит для самоподобных задач (деревья, «разделяй и властвуй»), но каждый вызов добавляет рамку стека — поэтому без базового случая происходит переполнение стека.
Простой цикл подсчета чище для обычной итерации; рекурсия сияет, когда задача содержит в себе меньшие её копии.
Что должно быть у рекурсивной процедуры для завершения? Выберите все подходящие варианты.
Самого базового случая недостаточно: если входные данные никогда не уменьшаются, базовый случай никогда не достигается, и рамки накапливаются до переполнения стека.
Разбор примера: проследите рекурсию
- Проследите
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. - Показывайте оба направления. Проследив только спуск или только возврат, вы потеряете половину баллов.
Рекурсия раскручивается от листьев вверх
Пройдите вычисление fib(4) в порядке фактического завершения вызовов: сначала разрешаются листья (базовые случаи), затем каждый родитель объединяет своих детей. Заметьте, что fib(2) вычисляется дважды — эта повторяющаяся работа объясняет медленную работу наивной рекурсии.
Что возвращает Factorial(4)?
4 × 3 × 2 × 1 = 24.
Что делает машина
- Каждый вызов требует собственной копии своих параметров и локальных переменных, поскольку
Factorial(3)иFactorial(2)— это разные вызовы с разными значениямиn. - Эти копии хранятся в кадре стека на стеке вызовов: по одному кадру на каждый активный вызов, содержащему параметры, локальные переменные и адрес возврата.
- Кадр добавляется (pushes) при каждом вызове и извлекается (pops) при возвращении. Именно поэтому значения возвращаются в обратном порядке по сравнению с порядком вызовов: стек вызовов работает как стек, точно как ADT из темы 10.
Расставьте события вычисления Factorial(4) в правильном порядке.
Ничего не перемножается на пути вниз; каждый вызов ждет. Перемножения происходят все при раскрутке стека.
Что может пойти не так
- Отсутствие базового случая или базового случая, который никогда не достигается: рекурсия никогда не останавливается, кадры накапливаются, и стек вызовов исчерпывает память. Это переполнение стека (stack overflow).
- Глубокая рекурсия: даже корректная рекурсия на миллион уровней требует миллион кадров, что может исчерпать память там, где цикл не потребил бы ничего.
- Дублирование работы: наивный рекурсивный Фибоначчи пересчитывает одни и те же значения экспоненциальное число раз. Исправьте это циклом или мемоизацией, сохраняя каждый результат при первом его вычислении.
Сопоставьте каждый термин рекурсии с его значением.
Рекурсия требует базового случая для остановки и рекурсивного случая для уменьшения задачи; каждый вызов добавляет рамку стека.
Рамка стека для вызова функции хранит:
Каждый фрейм хранит параметры вызова, локальные переменные и место для продолжения — чтобы вызовы не перекрывали друг друга.
Каждый выполняемый вызов хранит свои параметры и локальные переменные в собственном ____ на стеке вызовов.
Занимается при вызове, изымается при возврате. Именно поэтому значения возвращаются в обратном порядке по отношению к порядку вызовов.
Рекурсия или итерация
- Рекурсия подходит для самоподобных задач, где задача содержит меньшую копию самой себя: обход дерева, деление и властвование, такие как бинарный поиск и merge sort, и приведенная выше цепочка предков.
- Итерация подходит для всего остального и не требует дополнительной памяти для повторения.
- Любую рекурсивную задачу можно записать итеративно, и наоборот. Выбор зависит от того, какой подход яснее выражает суть задачи, в сравнении с затратами памяти на стек.
Рекурсивная процедура завершается сбоем из-за переполнения стека. Какое объяснение является верным?
Переполнение стека связано с фреймами, а не с арифметикой. Число, которое не помещается в регистр, — это арифметическое переполнение, совершенно иное явление.
Разбор примера: назовите риски
- Студент пишет рекурсивную процедуру, и она падает с ошибкой переполнения стека. Назовите две возможные причины.
- Отсутствует базовый случай, либо базовый случай никогда не достигается, так как входной параметр не уменьшается с каждым вызовом, поэтому вызовы продолжаются бесконечно, а кадры накапливаются.
- Рекурсия корректна, но слишком глубока: каждый из очень многих вызовов хранит свой собственный кадр стека, и стек вызовов исчерпывает память до достижения базового случая.
- Обе причины связаны с накоплением кадров. Укажите, что именно накапливается и почему это не прекращается.
Потерянные баллы
- Для рекурсии нужны оба условия: базовый случай и входной параметр, который уменьшается. Упоминание только базового случая — это лишь половина условия.
- При прослеживании показывайте вызовы, накапливающиеся до базового случая, и значения, возвращающиеся обратно. Оба направления оцениваются баллами.
- У каждого вызова есть собственные параметры и локальные переменные в своем собственном кадре стека. Именно поэтому рекурсия требует памяти, которая не нужна итерации.
- Переполнение стека (stack overflow) — это нехватка памяти стека из-за слишком большого количества кадров, а не арифметическое переполнение.
Вы поняли
- рекурсивная процедура требует базового случая, решаемого напрямую, и рекурсивного случая, который вызывает саму себя с меньшим входным значением
- проследите её в обоих направлениях: вызовы накапливаются до базового случая, затем значения возвращаются назад
- у каждого вызова есть свой собственный кадр стека на стеке вызовов, добавляемый при вызове и удаляемый при возврате, именно поэтому рекурсия требует памяти
- риски: отсутствие достижимого базового случая приводит к бесконечной рекурсии и переполнению стека, глубокая рекурсия исчерпывает память, а повторяющиеся вычисления требуют цикла или мемоизации