"Информатика", Семакин И.Г., Залогова Л.А., Русаков С.В., Шестакова Л.В.
Рекурсия — способ описать решение задачи через решение похожей, но меньшей задачи. Для этого процедура вызывает саму себя, меняя передаваемые данные так, чтобы приблизиться к завершению. Рекурсивный алгоритм должен содержать условие остановки: когда оно выполнено, новые вызовы больше не нужны, а управление возвращается по цепочке к предыдущим вызовам. Рекурсию используют для вычислений и обработки структур, которые удобно делить на подобные части.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Рекурсия — способ задания алгоритма, при котором он обращается к самому себе для решения задачи. Проще говоря, алгоритм решает исходную задачу, вызывая решение для её более простого варианта. Это удобно, когда большая задача естественно распадается на части, устроенные так же, как целое.
Рекурсивная процедура — процедура, которая прямо или косвенно вызывает саму себя. Прямой вызов виден в её собственном описании, а косвенный происходит через другую процедуру. Такое определение помогает понять, почему после начала выполнения может появиться цепочка вложенных вызовов.
Рекурсивный вызов — обращение процедуры к самой себе с новыми данными, приближающими решение к завершению. Например, при вычислении факториала число n можно заменить на n−1. Изменение данных важно: оно переводит вычисление к задаче, которую проще решить.
Условие завершения — проверка, при которой рекурсивные вызовы прекращаются и начинается возврат результатов. Его также называют базовым случаем: для него ответ можно получить без нового вызова процедуры. Оно нужно, чтобы цепочка вычислений имела конец.
Чтобы применить рекурсию, большую задачу представляют как задачу того же типа, но меньшего размера. Например, сумму нескольких элементов можно выразить через первый элемент и сумму остальных. Так задача постепенно упрощается, а решение для меньшей части становится основой для решения исходной задачи.
В процедуре нужны и рекурсивный вызов, и условие завершения. Вызов уменьшает задачу, а условие задаёт случай, который уже можно решить напрямую, без нового обращения к процедуре. Если оставить только вызов, процедура не остановится сама: компьютеру придётся хранить всё новые незавершённые вызовы.
Сначала один вызов запускает следующий и приостанавливается, затем следующий запускает ещё один. Так вызовы накапливаются до тех пор, пока не сработает условие завершения. После этого самый вложенный вызов заканчивается, управление возвращается к тому, который его запустил, и так продолжается до первого вызова.
При каждом вызове меняются параметры — данные, с которыми работает процедура. Их нужно изменять так, чтобы задача становилась меньше или движение шло к нужной границе. Если значение не меняется либо удаляется от условия завершения, базовый случай может оказаться недостижимым.
Одну и ту же задачу часто можно решить рекурсией или циклом. Цикл повторяет команды, пока выполняется условие, а рекурсия создаёт вызовы процедуры, которые возвращаются в обратном порядке. Рекурсивное описание иногда яснее показывает устройство задачи, но глубина цепочки должна оставаться разумной: для каждого вызова требуется память.
| Часть | Назначение | Что проверить |
|---|---|---|
| Условие завершения | Прекращает дальнейшие вызовы | Достижимо ли оно |
| Рекурсивный вызов | Решает уменьшенную задачу | Уменьшается ли задача |
| Параметры вызова | Передают данные следующему уровню | Изменяются ли они к завершению |
| Действия после вызова | Обрабатывают результат при возврате | Нужны ли они для решения |
Пользуйтесь таблицей как проверочным списком при составлении процедуры. Сначала найдите случай остановки, затем проследите, как вызов меняет задачу и переданные данные. В конце проверьте, требуется ли выполнять дополнительные действия после возврата результата.
Составим рекурсивную функцию для вычисления n!, учитывая, что 0! = 1. Факториал числа — произведение всех натуральных чисел от 1 до этого числа. Чтобы использовать рекурсию, выразим его через факториал меньшего числа: n! = n · (n−1)!, если n > 0.
Например, для 4 функция последовательно сводит вычисление к 3!, 2!, 1! и 0!. При возврате результаты умножаются: 1 · 1, затем 2 · 1, 3 · 2 и 4 · 6. Ответ: 4! = 24.
Нужно описать процедуру, которая выводит цифры числа справа налево. Последняя цифра числа получается как остаток от деления на 10, а число без этой цифры — как целая часть от деления на 10. Сначала выведем последнюю цифру, затем рекурсивно обработаем оставшуюся часть.
Для числа 527 сначала выводится 7, затем вызов для 52 выводит 2, а вызов для 5 — 5. Следующий вызов получает ноль и останавливает цепочку. Здесь цифры выводятся до рекурсивного вызова, поэтому они появляются в порядке от последней к первой; ответ: 725.
Найдём сумму элементов массива рекурсивно, передавая индекс текущего элемента. Сумму можно разложить на значение текущего элемента и сумму элементов после него. Для примера будем считать, что элементы нумеруются от 0, а индекс указывает на начало ещё не обработанной части массива.
Для массива [3, 5, 2] вызовы сводят сумму к 3 + сумме от индекса 1, затем к 5 + сумме от индекса 2 и далее к 2 + сумме от индекса 3. На границе возвращается 0, после чего частичные суммы складываются: 2, 7, 10. Ответ: сумма элементов равна 10.
Забывают условие завершения, и процедура вызывает себя снова при любых данных. Такую ошибку допускают, сосредоточившись на повторяющемся шаге и не предусмотрев простой случай. Проверьте, есть ли ветвь, которая заканчивает выполнение без нового вызова.
В рекурсивном вызове параметр не меняют в сторону условия завершения. Например, при вычислении факториала можно случайно передавать то же n, и базовый случай никогда не наступит. Проследите значения параметра на нескольких шагах и убедитесь, что они приближаются к остановке.
Условие завершения путают с рекурсивным шагом и останавливаются раньше, чем обработаны нужные данные. Это происходит, если базовый случай выбран для обычной части задачи или проверяется не та граница. Проверьте процедуру на минимальном примере и отдельно выясните, какие данные остаются необработанными при остановке.
Неверно учитывают, что стоит до вызова, а что после него. Вывод до вызова происходит при углублении, а действия после вызова — при возврате; из-за этого могут измениться результат или порядок вывода. Проверьте выполнение вручную на коротком примере, записывая действия при каждом входе и возврате.
Для создания рекурсивной процедуры нужны знания о процедурах, параметрах и условных операторах: они позволяют передать данные и выбрать между остановкой и новым вызовом. С циклами рекурсию связывает повторение действий; сравнение способов помогает выбрать более понятное решение и учесть глубину вызовов. Рекурсивный приём полезен при обработке вложенных структур и задач, которые естественно разбиваются на подобные подзадачи.
Чем рекурсивная процедура отличается от обычной?
Обычная процедура выполняет заданные команды, но сама себя не вызывает. Рекурсивная процедура прямо или через другие процедуры запускает себя снова с новыми данными.
Зачем в рекурсивной процедуре нужно условие завершения?
Оно задаёт случай, в котором новые вызовы прекращаются. Без такого условия процедура продолжала бы вызывать себя, пока не закончилась бы доступная память для хранения вызовов.
Что произойдёт, если параметр не приближается к условию завершения?
Базовый случай может так и не наступить, поэтому вызовы будут продолжаться. В итоге обычно переполняется стек вызовов — область памяти, где хранятся данные незавершённых процедур.
Как выполняются действия, записанные после рекурсивного вызова?
Они выполняются не сразу, а после того, как вложенный вызов завершится и вернёт управление. Поэтому такие действия происходят при возвращении по цепочке вызовов, от последнего к первому.
Можно ли заменить рекурсию циклом?
Часто одну задачу можно решить и рекурсией, и циклом. Цикл обычно не создаёт цепочку вызовов, а рекурсивный способ бывает удобнее, если задача естественно делится на подобные подзадачи.
1.2. Использование рекурсивных процедур
