§ 8. Рекурсия

Определения и обозначения

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

Рекурсивная функция — функция, которая во время выполнения вызывает саму себя, передавая данные для более простого случая. Она может применить к результату вызова дополнительные действия и вернуть итог. Такое определение помогает распознать рекурсию в программе: внутри функции должен быть вызов этой же функции.

Базовый случай — случай, для которого ответ известен сразу и рекурсивный вызов не нужен; он останавливает цепочку вызовов. Например, для факториала базовым случаем служит 0!, равный 1. Без такого условия функция не получит момента, когда нужно прекратить обращаться к себе.

Рекурсивный вызов — обращение функции к самой себе с изменёнными данными, приближающими выполнение к базовому случаю. В вычислении факториала вызов для n обращается к факториалу числа n−1. Изменение аргумента нужно, чтобы задача постепенно стала той, чей ответ уже известен.

Как это устроено

Рекурсивное решение строится из двух частей: простого случая с известным ответом и правила для остальных случаев. Правило сводит исходную задачу к похожей, но меньшей, поэтому её можно решать тем же способом. Например, чтобы найти сумму чисел от 1 до 5, достаточно прибавить 5 к сумме чисел от 1 до 4. Такая схема удобна, когда подзадачи устроены так же, как исходная задача.

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

Факториал числа n — произведение всех натуральных чисел от 1 до n, причём 0! = 1. Для любого n больше нуля верно: n! = n · (n−1)!. Поэтому факториал 4 можно разложить так: 4! = 4 · 3!, 3! = 3 · 2!, 2! = 2 · 1!, 1! = 1 · 0!. Когда функция доходит до 0!, она получает готовое значение 1, а затем выполняет умножения.

Каждый вызов функции обрабатывается отдельно: программа хранит его аргумент и место, куда нужно вернуться после получения ответа. Поэтому вызов factorial(4) ждёт результата factorial(3), тот — factorial(2), и так далее. Когда базовый случай возвращает 1, выполнение идёт обратно: сначала считается 1 · 1, затем 2 · 1, затем 3 · 2 и 4 · 6. Такой возврат объясняет, как из ответа для меньшей задачи получается ответ для большей.

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

Элементы рекурсивного алгоритма

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

Разбор задач

Факториал натурального числа

Составим функцию для вычисления n!, учитывая, что 0! = 1. По определению для n больше нуля факториал равен n · (n−1)!. Значит, функции достаточно вернуть 1 при нуле, а во всех остальных случаях умножить n на результат вызова для n−1.

1. Задаём базовый случай: если n = 0, функция возвращает 1.
2. Для n больше нуля вызываем factorial(n−1). Аргумент уменьшается, поэтому после конечного числа вызовов будет достигнут ноль.
3. Возвращаем n · factorial(n−1). Например, factorial(3) приводит к вычислению 3 · 2 · 1 · 1 = 6.

Ответ: правило функции — при n = 0 вернуть 1, иначе вернуть n · factorial(n−1). Так учитывается и определение факториала, и необходимое условие остановки.

Сумма чисел от 1 до n

Нужно найти сумму целых чисел от 1 до заданного n. Сумма до n получается, если к сумме до n−1 прибавить само n. При n = 0 чисел для сложения нет, поэтому сумма равна нулю; это удобный базовый случай.

1. Если n = 0, возвращаем 0, поскольку сумма пустого набора равна нулю.
2. Иначе вызываем sum(n−1), чтобы получить сумму предыдущих чисел.
3. К результату вызова прибавляем n: возвращаем n + sum(n−1). Для n = 3 это даст 3 + 2 + 1 + 0 = 6.

Ответ: функция возвращает 0 при n = 0, а при n больше нуля — n + sum(n−1). Перед применением правила следует убедиться, что n — неотрицательное целое число.

Проверка числа на палиндром

Палиндром читается одинаково слева направо и справа налево, например 12321. Для проверки сравним первую и последнюю цифры: если они разные, число не палиндром. Если цифры совпали, можно отбросить их и проверить середину тем же способом.

1. Для записи из одной цифры ответ положительный: такая запись читается одинаково в обоих направлениях. Пустая оставшаяся часть после удаления совпавших крайних цифр тоже считается базовым случаем с положительным ответом.
2. Если крайние цифры не равны, возвращаем ложь и прекращаем проверку.
3. Если они равны, удаляем их и рекурсивно проверяем оставшуюся часть. Например, у 12321 крайние цифры равны 1, после их удаления остаётся 232, которое также симметрично.

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

Типичные ошибки

Первая ошибка — не задать базовый случай, рассчитывая, что вызовы сами закончатся. Но функция не может догадаться, когда прекращать работу, поэтому она продолжает обращаться к себе. Проверьте, есть ли условие, при котором рекурсивный вызов не выполняется и сразу возвращается известный ответ.

Вторая ошибка — оставить аргумент без изменений или менять его не в сторону базового случая. Так вызовы повторяют одну и ту же задачу либо удаляются от остановки. Для самопроверки выпишите несколько первых аргументов: в примере с факториалом должны получиться n, n−1, n−2 и так далее, пока не встретится 0.

Третья ошибка — неверно указать ответ в базовом случае, например принять 0! за 0. Тогда цепочка вызовов остановится, но вернёт неправильное значение, которое испортит все предыдущие вычисления. Сверьте базовый ответ с условием задачи или определением и проверьте функцию на самом простом аргументе.

Четвёртая ошибка — получить результат рекурсивного вызова, но не использовать его при вычислении текущего ответа. Тогда связь между подзадачей и исходной задачей теряется. Проверьте, что значение вызова входит в формулу результата: для факториала оно умножается на n, а для суммы к нему прибавляется n.

Связь с другими темами

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

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

Что запомнить

• Рекурсивный алгоритм вызывает сам себя для решения более простой задачи.
• В рекурсивной функции необходим базовый случай.
• Каждый вызов должен приближать данные к базовому случаю.
• Результат рекурсивного вызова используют для получения текущего ответа.
• Глубокая цепочка вызовов расходует память.
• Одну и ту же задачу иногда можно решить и рекурсией, и циклом.