Рекурсия и рекуррентные соотношения

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

База и рекурсивный шаг

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

Запись F(n) обозначает значение функции F при аргументе n. Для определённости возьмём правило из EGE-16-0004 ↗: F(n)=n при n<10 и F(n)=n-1+F(n-1) при n\ge10.

В первой части ответ известен без дальнейших обращений к функции. Это база рекурсии. Вторая часть задаёт рекурсивный шаг: чтобы найти текущее значение, нужно предыдущее. При вычислении F(11) сначала возникает зависимость от F(10), затем от F(9). Последнее значение известно: F(9)=9. После этого можно завершить отложенные действия:

F(10)=9+9=18, затем F(11)=10+18=28.

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

Почему вычисление заканчивается

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

В примере выше аргумент уменьшается на единицу. Для любого целого n\ge10 он дойдёт до 9, после чего новые вызовы не нужны. Сама граница 10 ещё относится к рекурсивному шагу, поскольку условие базы строгое.

Уменьшение аргумента не является обязательным свойством рекурсии. Если база задана при n\ge2025, а переход ведёт к n+2, движение вверх приближает к остановке. Начало с 2022 даёт 2022\to2024\to2026. Пропуск числа 2025 не мешает: вся область выше границы тоже является базой.

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

От раскрытия к сокращению

Повторная подстановка раскрывает ту часть зависимости, которая нужна для вопроса. Если правило имеет вид F(n)=a(n)+F(n-d), то a(n) обозначает прибавляемое на текущем шаге число, а d — величину шага. Два раскрытия дают:

F(n)=a(n)+a(n-d)+F(n-2d).

Если требуется разность F(n)-F(n-2d), общий остаток исчезает и остаются два слагаемых. Такое равенство применимо, когда оба раскрываемых аргумента относятся к рекурсивной части определения. Переход через базу по формуле шага был бы неверным.

Для умножения связь похожа. Пусть b(n) обозначает множитель в правиле F(n)=b(n)F(n-d). Тогда:

F(n)=b(n)b(n-d)F(n-2d).

В отношении к F(n-2d) последняя функция сокращается, если её значение ненулевое. В сумме или разности сначала нужно вынести общий множитель всего числителя. Сокращать отдельное слагаемое со знаменателем, оставляя другие без деления, нельзя.

Цепочка, несколько ветвей и две функции

Если каждый шаг требует одного следующего вызова, вычисление идёт по цепочке. Если нужны несколько вызовов, появляются ветви. Учебный пример: F(1)=F(2)=1 и F(n)=F(n-1)+F(n-2) при n>2. Для F(5) нужны F(4) и F(3). Но для самого F(4) также требуется F(3). Если программа не сохраняет готовые результаты, одно и то же значение будет вычислено повторно.

Сохранение результатов для повторного использования называется мемоизацией. В этом примере после первого вычисления F(3) его значение можно взять из памяти. Так исчезает повторная работа, но первый путь до базы остаётся той же длины: до получения результата все вызовы на этом пути ещё ожидают завершения.

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

Количество имён функций не определяет число ветвей. В формуле F(n)=2(G(n-3)+8) для одного значения F требуется одно значение G. А выражение 2G(n)+G(n-1) требует двух значений: G(n) и G(n-1). Каждая зависимость прослеживается до базы. Если функции вызывают друг друга, на каждом шаге учитываются и имя функции, и аргумент.

Таблица вместо вложенных вызовов

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

Для EGE-16-0024 ↗ база F(n)=n начинается при n\ge2025, а ниже действует F(n)=n+F(n+2). Для требуемых значений достаточно двух базовых ячеек и трёх шагов вниз:

f = {2025: 2025, 2026: 2026}
for n in range(
    2024, 2021, -1
):
    f[n] = n + f[n + 2]
print(f[2022] - f[2023])

Цикл проходит аргументы 2024,2023,2022. На каждом шаге ячейка с аргументом на два больше уже заполнена. Получаются F(2024)=4050, F(2023)=4048 и F(2022)=6072; программа выводит 2024.

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

Значение функции и вывод программы

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

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

Применение в заданиях

Как найти разность огромных значений, раскрыв лишь несколько звеньев? Почему две соседние точки при шаге через два могут потребовать разных базовых значений?

Оба вопроса разобраны на реальных условиях в статье «Задание №16. Рекурсивные функции и сокращение вычислений».