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

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

Что такое рекуррентное соотношение

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

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

Если функция при \(n>0\) вызывает себя один раз с аргументом \(n-1\), то глубина цепочки равна \(n\) с точностью до выбранного базового случая. Если вызовов несколько, возникает дерево рекурсии, и число вызовов нужно складывать по всем ветвям. Этому помогает размер дерева рекурсивных вызовов.

Как составить формулу для результата

Удобный порядок действий такой:

1. Выписать базовый случай и его результат: это начальное условие, например \(F(0)=1\).
2. Рассмотреть один обычный вызов функции с аргументом \(n\).
3. Заменить рекурсивный вызов его обозначением \(F(n-1)\), \(F(n-2)\) или другим подходящим выражением.
4. Добавить действия, которые выполняются до или после рекурсивного вызова.
5. Проверить формулу на небольшом аргументе вручную.

Например, функция может возвращать сумму чисел от \(1\) до \(n\). Если сначала вызывается функция для \(n-1\), а затем к её результату прибавляется \(n\), получается \(F(n)=F(n-1)+n\). Если результат умножается на \(n\), получается \(F(n)=n\cdot F(n-1)\). Если функция возвращает константу, добавленную к результату, эта константа также входит в соотношение.

Как считать число вызовов

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

Здесь \(1\) — текущий вызов, а \(n_1,\ldots,n_k\) — аргументы всех рекурсивных вызовов, сделанных из него. Если рекурсивных вызовов нет, сумма отсутствует. Например, для одного вызова с аргументом \(n-1\) имеем \(C(n)=1+C(n-1)\).

Для двух одинаковых вызовов f(n-1) формула будет \(C(n)=1+2C(n-1)\). Для вызовов f(n-1) и `f(n-2)\(—\)C(n)=1+C(n-1)+C(n-2)$. Такая запись особенно важна для алгоритмов, где одна и та же подзадача вычисляется много раз.

Разобранный пример: два рекурсивных вызова

Рассмотрим функцию, которая при \(n>0\) вызывает себя для \(n-1\) и ещё раз для \(n-2\), а затем складывает результаты. Базовый случай: при \(n\le 0\) функция сразу возвращает 1. Требуется составить формулу для числа вызовов при начальном аргументе \(n\) и найти это число для \(n=4\).

1function F(n)
2    if n <= 0 then
3        return 1
4    return F(n - 1) + F(n - 2)

Формулу результата для этого же фрагмента можно записать отдельно. Пусть \(R(n)\) — возвращаемое значение. Тогда \(R(n)=1\) при \(n\le0\), а при \(n>0\) выполняется \(R(n)=R(n-1)+R(n-2)\). Это похоже на последовательность Фибоначчи, но начальные значения здесь зависят от базового случая.

Проверка и связь с другими задачами

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

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

Quick-test