Рекурсия в Python: пошаговый разбор задания 16 ЕГЭ

Два вопроса к любой рекурсивной формуле

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

Возьмём собственный учебный пример для натуральных n: F(1) = 2, а при n ≥ 2 — F(n) = F(n − 1) + 3n. Аргумент уменьшается на единицу, поэтому при допустимом n вычисления дойдут до F(1).

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

Разбираем F(4) без запуска программы

Сначала раскрываем вызовы до известного значения:

F(4) = F(3) + 12
F(3) = F(2) + 9
F(2) = F(1) + 6
F(1) = 2

Теперь возвращаемся снизу вверх. F(2) = 2 + 6 = 8; F(3) = 8 + 9 = 17; F(4) = 17 + 12 = 29.

Таблица особенно удобна, если нужно несколько соседних значений. Каждое следующее строится из уже найденного предыдущего.

Записываем определение в Python

Условие остановки ставим до рекурсивного вызова. Для наших натуральных аргументов функция выглядит так:

def F(n):
    if n == 1:
        return 2
    return F(n - 1) + 3 * n

print(F(5))  # 44

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

Если вызовов два: не пересчитываем одинаковое

У формулы G(n) = G(n − 1) + G(n − 2) одни и те же значения понадобятся несколько раз. Зададим G(0) = 0 и G(1) = 1. Декоратор @cache запоминает результат для каждого аргумента:

from functools import cache

@cache
def G(n):
    if n < 2:
        return n
    return G(n - 1) + G(n - 2)

print(G(6))  # 8

Последовательность от G(0) до G(6): 0, 1, 1, 2, 3, 5, 8. Кеш помогает при повторных вычислениях, но не исправляет неверную формулу и не устраняет ограничение глубины рекурсии. functools.cache доступен с Python 3.9; подробнее — в документации Python.

Когда удобнее заменить рекурсию циклом

Для первой формулы F(n) достаточно хранить предыдущее значение. Тот же расчёт F(5) можно выполнить снизу вверх:

value = 2
for n in range(2, 6):
    value += 3 * n
print(value)  # 44

Правая граница range(2, 6) не включается: цикл обрабатывает n от 2 до 5. Для больших n такой вариант не накапливает вложенные вызовы.

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

Частые ошибки

• Потерять базовый случай или поставить его после вызова.
• Подставить n вместо n − 1.
• Выполнить только самый внешний шаг и забыть раскрыть F(n − 1).
• Перепутать возвращаемое значение с тем, что печатает функция.
• Сразу увеличивать предел рекурсии вместо выбора подходящего алгоритма.

Проверьте себя

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.