"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Рекурсия — способ описать решение, в котором задача сводится к такой же задаче меньшего размера. В программе рекурсивная функция вызывает саму себя, пока не встретит базовый случай — условие, позволяющее сразу получить ответ. Затем результат возвращается через цепочку вызовов. Такой подход помогает описывать факториалы, обработку деревьев и поиск в упорядоченном массиве, но требует следить за глубиной вызовов и расходом памяти.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Рекурсия — способ описания процесса, при котором он обращается к самому себе. Например, чтобы решить задачу для большого числа, можно свести её к такой же задаче для числа поменьше. Это полезно, когда исходную задачу естественно разбить на похожие подзадачи.
Рекурсивная функция — функция, которая вызывает саму себя. Вызов бывает прямым, когда функция обращается к себе по собственному имени, или косвенным, когда к ней приводит цепочка вызовов других функций. Это понятие позволяет описывать повторяющиеся вычисления компактно.
Базовый случай — условие, при котором рекурсивные вызовы прекращаются и результат находится непосредственно. Например, для вычисления факториала таким случаем служит 0! = 1. Базовый случай нужен, чтобы вычисление имело точку остановки.
Рекурсивный вызов — обращение функции к самой себе с изменёнными аргументами. Обычно он решает задачу меньшего размера, например для числа n − 1 вместо n. Такой переход постепенно подводит вычисление к базовому случаю.
Сложную задачу можно решить, если представить её как знакомую задачу меньшего размера и отдельно определить самый простой вариант. Например, для вычисления факториала большого числа достаточно знать факториал предыдущего числа. Такое разложение работает потому, что подзадачи сохраняют структуру исходной задачи, а значит, для них подходит тот же способ решения.
В рекурсивной функции сначала проверяют, достигнут ли базовый случай. Если да, функция сразу возвращает готовый ответ; если нет, она вызывает себя для более простой задачи. После завершения вложенного вызова текущая функция получает его результат и выполняет оставшуюся часть вычисления. Поэтому рекурсивное описание состоит из условия остановки и перехода к следующей задаче.
Аргументы каждого вызова должны изменяться так, чтобы приближать вычисление к базовому случаю. При факториале уменьшают n на единицу, а при бинарном поиске сокращают границы области поиска. Если аргумент не меняется или движется в противоположную сторону, базовый случай может оказаться недостижимым. Тогда программа создаёт новые вызовы, пока не исчерпает допустимую глубину или память.
Когда функция вызывает себя, её текущие данные нельзя потерять: после ответа вложенного вызова работа должна продолжиться с того же места. Программа сохраняет аргументы и точку продолжения в специальной области памяти — стеке вызовов. Сначала завершается самый глубокий вызов, затем управление возвращается к предыдущему, и так далее. Поэтому отложенные вычисления заканчиваются в порядке, обратном порядку их начала.
Ту же задачу часто можно решить циклом, и такой вариант обычно не создаёт длинную цепочку вызовов. Рекурсия делает алгоритм понятнее, когда задача по своей структуре распадается на похожие подзадачи, например узлы дерева или половины массива. За наглядность приходится платить временем на вызовы и памятью для хранения незавершённых вычислений. Выбирают способ, исходя из ясности алгоритма, возможной глубины и требований к ресурсам.
| Характеристика | Рекурсивный способ | Итерационный способ |
|---|---|---|
| Как организовано повторение | Функция вызывает себя для подзадачи | Повторение организовано циклом |
| Условие завершения | Достигнут базовый случай | Условие цикла перестало выполняться |
| Как сохраняются промежуточные вычисления | В стеке вызовов | В переменных цикла |
| Использование памяти | Растёт с глубиной вызовов | Часто ограничено несколькими переменными |
| Когда способ особенно удобен | При естественном делении на похожие подзадачи | При последовательном повторении однотипных действий |
Сравнивайте способы для одной и той же задачи: таблица показывает, откуда берутся повторения и где хранятся промежуточные данные. Если задача естественно распадается на подзадачи, рекурсивная запись может быть понятнее. Если важны экономия памяти и простое повторение, часто удобнее цикл.
Задача 1. Составить рекурсивную функцию для вычисления факториала натурального числа n. Используем определение n! = n · (n − 1) · … · 1. Чтобы вычисление остановилось, зададим 0! = 1: рекурсивный переход будет уменьшать аргумент до нуля.
Ответ: factorial(n) = 1 при n = 0, иначе n · factorial(n − 1). Передавать функции нужно неотрицательное целое n; при положительном n каждый вызов уменьшает аргумент на единицу.
Задача 2. Составить рекурсивную функцию для суммы цифр неотрицательного целого числа n. Последнюю цифру можно получить как n mod 10, а оставшуюся часть числа — как n div 10. Так число с каждым вызовом теряет один разряд.
Ответ: sumDigits(n) = n при n < 10, иначе n mod 10 + sumDigits(n div 10). Для 527 сумма равна 14. Для нуля базовый случай также возвращает правильную сумму цифр — 0.
Задача 3. Найти заданное значение x в упорядоченном массиве методом деления пополам. Функция получает границы l и r текущей области поиска. Если искомое значение не совпадает со средним элементом, упорядоченность позволяет отбросить половину области.
Ответ: рекурсивный бинарный поиск возвращает индекс найденного элемента либо признак отсутствия. После каждого вызова область становится меньше, а случай l > r гарантирует завершение, в том числе если исходный массив пуст.
Не задан базовый случай. Функция продолжает вызывать себя, потому что ни при одном условии не возвращает ответ сразу. Так бывает, если описать только общий переход и забыть самый простой вход. Проверьте, для какого минимального значения задача решается непосредственно, и предусмотрите для него отдельный результат.
Аргумент не приближается к базовому случаю. Если значение не меняется или изменяется неверно, цепочка вызовов не сокращается. Ошибку допускают, сосредоточившись на формуле результата и не проследив за аргументом. Подставьте небольшой вход и выпишите аргументы вызовов: они должны шаг за шагом дойти до условия остановки.
Неверно задан базовый случай или его результат. Ошибка в границе может нарушить работу на нуле, единице или пустой области поиска. Иногда базовый случай срабатывает слишком рано, а иногда не срабатывает на допустимом граничном значении. Проверьте простейшие входы вручную и убедитесь, что возвращаемый ответ действительно соответствует условию задачи.
Игнорируются затраты памяти. Каждый незавершённый вызов хранит свои данные, поэтому глубокая рекурсия занимает место в стеке. Это легко упустить, если смотреть только на короткую запись функции. Оцените максимальное число вложенных вызовов и при большой глубине рассмотрите цикл или другой алгоритм.
Для работы с рекурсией нужны знания о функциях, параметрах, возвращаемых значениях, условном операторе и вызове функции: без них нельзя задать переход и остановку. С математической индукцией её связывает устройство рассуждения: есть простой начальный случай и переход к случаю большего размера. Рекурсивные алгоритмы особенно полезны при обработке деревьев, вложенных структур и задач, которые естественно разделяются на подзадачи. В каждом случае важно определить, как уменьшить задачу и что считать простейшим случаем.
Что такое рекурсия простыми словами?
Это способ решать задачу, сводя её к такой же, но меньшей. Например, факториал числа выражается через факториал предыдущего числа.
Зачем рекурсивной функции нужен базовый случай?
Базовый случай задаёт ответ без нового рекурсивного вызова. Он останавливает цепочку вызовов, иначе программа может повторять вычисления бесконечно.
Что произойдёт, если рекурсивный вызов не приближает к базовому случаю?
Функция продолжит вызывать себя, не доходя до условия остановки. В итоге программа может исчерпать память стека и завершиться с ошибкой.
Как программа выполняет и завершает вложенные рекурсивные вызовы?
Перед новым вызовом программа сохраняет данные текущего: аргументы и место, где нужно продолжить работу. Когда найден базовый случай, вызовы завершаются в обратном порядке, и каждый использует результат следующего.
Всегда ли рекурсивное решение лучше цикла?
Нет. Рекурсия бывает нагляднее для задач, которые делятся на подзадачи, но вызовы требуют дополнительной памяти и времени. Простое повторение часто эффективнее выразить циклом.
§ 61. Рекурсия
