§ 15. Рекуррентные соотношения и рекурсивные алгоритмы

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

Рекуррентное соотношение — правило, по которому каждый член последовательности выражается через один или несколько предыдущих членов. Например, запись aₙ₊₁ = aₙ + 3 означает, что следующий член на три больше текущего. Такое правило нужно, когда последовательность удобнее строить шаг за шагом, а не задавать формулой для любого номера.

Начальные условия — заданные значения первых членов последовательности, необходимые для однозначного вычисления остальных. Если известно лишь, что aₙ₊₁ = aₙ + 3, то возможны последовательности 1, 4, 7… и 4, 7, 10… . Начальные значения закрепляют конкретный вариант, от которого начинаются вычисления.

Рекурсивный алгоритм — алгоритм, который решает задачу, обращаясь к самому себе для решения более простой подзадачи. Например, для вычисления факториала n! можно сначала вычислить (n − 1)!, а затем умножить результат на n. Такой способ удобен, если задача естественно раскладывается на похожие задачи меньшего размера.

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

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

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

Члены последовательности вычисляют по порядку: сначала записывают известные начальные значения, затем находят ближайший неизвестный член. Полученный результат становится исходным для следующего шага, поэтому нельзя перескочить через нужные предыдущие значения, если они участвуют в формуле. Например, при aₙ₊₁ = aₙ + 3 сначала находят a₂, а уже затем используют его для вычисления a₃.

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

Последовательность Фибоначчи задаётся равенством Fₙ = Fₙ₋₁ + Fₙ₋₂ при n ≥ 3 и начальными условиями F₁ = 1, F₂ = 1. Для вычисления очередного числа нужны два предыдущих, поэтому одного сохранённого значения недостаточно. Рекурсивный алгоритм для Fₙ передаёт себе задачи вычислить Fₙ₋₁ и Fₙ₋₂, а затем складывает результаты.

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

Рекуррентное задание последовательности и рекурсивный алгоритм

Сначала определите, что именно нужно получить: последовательность значений или ответ алгоритма. Затем найдите, что считается началом вычисления и как используется результат предыдущего шага. Последняя строка показывает, что похожая идея для Фибоначчи может быть записана и как правило для последовательности, и как алгоритм.

Разбор задач

Задача 1. Заданы a₁ = 4 и aₙ₊₁ = aₙ + 3. Найдите a₂, a₃ и a₄. Здесь каждый новый член получается из предыдущего, поэтому будем двигаться по порядку и подставлять уже найденное значение.

1. Для a₂ подставляем a₁: a₂ = 4 + 3 = 7.
2. Для a₃ используем найденный a₂: a₃ = 7 + 3 = 10.
3. Для a₄ используем a₃: a₄ = 10 + 3 = 13.

Ответ: a₂ = 7, a₃ = 10, a₄ = 13. Каждый раз прибавляется одно и то же число, что позволяет проверить вычисления: члены последовательности возрастают на три.

Задача 2. Составьте рекуррентное соотношение и начальные условия для чисел Фибоначчи, затем найдите первые шесть членов. Следующий член определяется суммой двух предыдущих, значит, для старта нужно задать два значения. Возьмём обычное начало последовательности: F₁ = 1 и F₂ = 1.

1. Записываем правило: Fₙ = Fₙ₋₁ + Fₙ₋₂ при n ≥ 3.
2. Уже известны F₁ = 1 и F₂ = 1; по правилу F₃ = 1 + 1 = 2.
3. Продолжаем: F₄ = 1 + 2 = 3, F₅ = 2 + 3 = 5.
4. Для шестого члена складываем два предыдущих: F₆ = 3 + 5 = 8.

Ответ: F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ при n ≥ 3; первые шесть членов — 1, 1, 2, 3, 5, 8. Начальных значений два, потому что правило использует два предыдущих члена.

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

1. Если n = 0, вернуть 1: это базовый случай, соответствующий равенству 0! = 1.
2. Если n > 0, вернуть n · factorial(n − 1).
3. Для 4 получаем цепочку: factorial(4) = 4 · factorial(3) = 4 · 3 · factorial(2).
4. Продолжаем: 4 · 3 · 2 · factorial(1) = 4 · 3 · 2 · 1 · factorial(0) = 24.

Ответ: алгоритм возвращает 24. Вызовы дошли до factorial(0), поэтому остановились; затем результаты последовательно использовались для вычисления factorial(1), factorial(2), factorial(3) и factorial(4).

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

Записывают правило перехода, но забывают начальные условия. Часто кажется, что само правило уже полностью задаёт последовательность, хотя от разных стартовых значений получаются разные ряды. Проверьте себя: можете ли вы вычислить первый член, не вводя дополнительных предположений; если нет, укажите нужные начальные значения.

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

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

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

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

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

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

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

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

• Рекуррентное соотношение задаёт член последовательности через предыдущие члены.
• Для вычисления последовательности по рекуррентному правилу нужны начальные условия.
• Рекурсивный алгоритм вызывает сам себя для решения более простой подзадачи.
• Базовый случай прекращает дальнейшие рекурсивные вызовы.
• Каждый рекурсивный вызов должен приближать задачу к базовому случаю.
• Рекурсивное решение нужно проверять на завершение и правильность результата.