Задание 16: рекурсивные алгоритмы и рекуррентные соотношения

Задание 16 (повышенный уровень): вычисляем значение рекурсивной функции, заданной соотношением.

Рекурсия — это определение функции через саму себя: значение F(n) выражается через значения F при меньших аргументах. Обязателен базовый случай, на котором рекурсия останавливается.

Что проверяет задание

Дано определение функции в виде рекуррентного соотношения — например, «F(n) = F(n−1) + F(n−2) + n, причём F(1) = F(2) = 1». Нужно найти конкретное значение F(k), сумму цифр результата или количество вызовов. Считать руками глубокую рекурсию невозможно; зато на Python такое определение переписывается почти дословно.

От соотношения к коду

Главный навык — перевести математическую запись в функцию. Сравните:

Собираем функцию и вычисляем нужное значение:

def F(n):
    if n <= 2:                       # базовый случай
        return 1
    return F(n - 1) + F(n - 2) + n   # рекуррентное соотношение

print("F(1..7):", [F(i) for i in range(1, 8)])
print("F(10) =", F(10))

Вывод:

F(1..7): [1, 1, 5, 10, 20, 36, 63]
F(10) = 296

Программа сама раскрутила всю рекурсию. Обратите внимание: значения удобно печатать «лесенкой» F(1), F(2), … — так видно, как они нарастают, и легко свериться с условием задачи.

Мемоизация: когда без неё долго

Наивная рекурсия пересчитывает одни и те же значения много раз: F(n−1) и F(n−2) оба обращаются к F(n−3) и так далее. Для больших n это экспоненциально медленно. Лечится мемоизацией — запоминанием уже вычисленных значений. В Python это одна строка-декоратор:

from functools import lru_cache

@lru_cache(None)                    # кэшируем результаты
def F(n):
    if n <= 2:
        return 1
    return F(n - 1) + F(n - 2) + n

print("F(30) =", F(30))             # мгновенно даже для большого n
print("сумма цифр F(30):", sum(int(c) for c in str(F(30))))

Вывод:

F(30) = 4674396
сумма цифр F(30): 39

На КЕГЭ привыкайте сразу ставить @lru_cache(None) над рекурсивной функцией — это бесплатная страховка от таймаута, ничего не меняющая в логике.

Линейная рекурсия и накопление

Не всякая рекурсия двойная. Часто соотношение линейное: F(n) выражается через одно предыдущее значение. Пример: «G(1) = 1; G(n) = G(n−1) + 2·n». Найти G(5).»

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

print("G(1..5):", [G(i) for i in range(1, 6)])
print("G(5) =", G(5))

Вывод:

G(1..5): [1, 5, 11, 19, 29]
G(5) = 29

Подсчёт количества вызовов

Иногда спрашивают не значение, а сколько раз будет вызвана функция при вычислении F(k). Это считается тем же приёмом — заведём счётчик. Здесь мемоизацию НЕ ставим, ведь нужно посчитать именно все вызовы «наивной» рекурсии:

calls = 0

def F(n):
    global calls
    calls += 1                       # фиксируем каждый вызов
    if n <= 2:
        return 1
    return F(n - 1) + F(n - 2) + n

F(10)
print("число вызовов F при вычислении F(10):", calls)

Вывод:

число вызовов F при вычислении F(10): 109

Рекурсия от двух аргументов

В заданиях посложнее функция зависит от двух параметров — это уже почти динамическое программирование. Классический пример — число сочетаний (треугольник Паскаля): «C(n, 0) = C(n, n) = 1; C(n, k) = C(n−1, k−1) + C(n−1, k)». Запишем дословно с мемоизацией:

from functools import lru_cache

@lru_cache(None)
def C(n, k):
    if k == 0 or k == n:
        return 1
    return C(n - 1, k - 1) + C(n - 1, k)

print("C(5,2) =", C(5, 2))
print("строка Паскаля для n=5:", [C(5, k) for k in range(6)])

Вывод:

C(5,2) = 10
строка Паскаля для n=5: [1, 5, 10, 10, 5, 1]

Для двух аргументов мемоизация особенно важна: без неё число повторных вызовов растёт лавинообразно. Декоратор @lru_cache(None) кэширует по паре (n, k) и превращает экспоненту в быстрый расчёт.

Типичные ловушки

• Базовый случай. Без условия остановки рекурсия уйдёт в бесконечность. Всегда сначала пишите базу.
• Граница базы. «F(1)=F(2)=1» — это if n <= 2, а не n == 1. Внимательно к тому, сколько значений заданы напрямую.
• Мемоизация и подсчёт вызовов несовместимы. Если считаете число вызовов — не ставьте кэш, иначе повторные вызовы исчезнут.
• Сумма цифр vs само значение. Часто в ответе требуется именно сумма цифр или последняя цифра — перечитайте вопрос.

Итог

• Рекуррентное соотношение переводится в Python дословно: сначала базовый случай, затем формула через F меньших аргументов.
• Для скорости ставьте @lru_cache(None) — но снимайте его, если нужно посчитать число вызовов.
• Читайте, что именно требуется: значение, сумма цифр, последняя цифра или количество вызовов.