Задание 16: Рекуррентные выражения. Вычисление функции

1. Общая информация о задании

Уровень сложности: базовый
Максимальный балл: 1
Примерное время выполнения: около 5 минут

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

Задания: N16. Рекурсия | N16. Рекурсия хард

2. Что такое рекуррентная функция

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

Типичный вид:

F(n) = <база>, если n <= k
F(n) = <выражение с F(n-1), F(n-2), ...>, иначе

Пример с двумя аргументами:

F(n, m) = <база>, если n = 0 или m = 0
F(n, m) = <выражение с F(n-1, m) и/или F(n, m-1)>, иначе

3. Алгоритм решения

Записать условие задания: определение функции и значения аргументов, при которых нужно вычислить результат.
Определить базовые случаи (при каких значениях аргументов функция возвращает число, а не вызывает себя).
Двигаться «сверху вниз»: записывать цепочку вызовов, пока не дойдём до базовых случаев.
Двигаться «снизу вверх»: подставлять вычисленные значения обратно в незакрытые вызовы.
Записать итоговый ответ.

4. Типичные конструкции в заданиях ЕГЭ 2026

Конструкция	Что нужно сделать
`F(n) = F(n-1) + F(n-2)` (числа Фибоначчи)	Строить последовательность от базы вверх
`F(n, m) = F(n-1, m) + F(n, m-1)`	Строить двумерную таблицу значений
`F(n) = 2*F(n-1) + n`	Вычислять шаг за шагом, подставляя n
Функция с несколькими ветками `if`	Следить за условием на каждом шаге

5. Решение на Python

5.1. Рекурсивная функция

Иногда удобнее написать рекурсивную функцию и получить ответ за секунды. Пример:

# Пример: F(1) = 1, F(2) = 1, F(n) = F(n-1) + 2*F(n-2) + n при n > 2
# Найти F(7)

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

print(F(7))

5.2. Через списки

Лимит рекурсии 1000 символов, если числа больше, удобно применять списки. Пример:

# Пример: F(n)=n, если n<5
# F(n)=2n×F(n−4), если n≥5
# Чему равно значение функции (F(13766)−9×F(13762))/F(13758)

F = [0] * 13800 # создаем список из нулей в количестве чуть больше чем наше число
for n in range(13800): # перебор до макс позиции
    if n < 5: # условия из задания
        F[n] = n
    if n >= 5:
        F[n] = 2 * n * F[n - 4] # важно: все круглые скобки заменяем на квадратные, т.к. работаем не с функцией а с позициями списка

print((F[13766] - 9 * F[13762]) // F[13758])

5.3. Аналитически (вручную)

Если числа большие, и функция рекрсивна, можно написать через факториал числа. Пример:

# Пример: F(n)=n, если n<5
# F(n)=2n×F(n−4), если n≥5
# Чему равно значение функции (F(13766)−9×F(13762))/F(13758)

тут_будет_картинка_с_решением

5.4. Через увеличение лимита рекурсии

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

import sys
sys.setrecursionlimit(20000)

# Пример: F(n)=2×(G(n−3)+8),
# G(n)=2×n, если n<10
# G(n)=G(n−2)+1, если n≥10
# Чему равно значение выражения F(15548)?

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

def F(n):
    return 2 * (G(n - 3) + 8)

print(F(15548))

sys.setrecursionlimit — позволяет увеличить лимит (базовый 1000) чтобы избежать ошибки функции. Осторожно, при больших значениях уйти в бесконечную обработку из-за загрузки памяти.

5.5. Через lru_cache

Для функций с двумя аргументами используем мемоизацию через lru_cache, чтобы не считать одно значение дважды:

from functools import lru_cache

# Пример: F(0, m) = m, F(n, 0) = n, F(n, m) = F(n-1, m) + F(n, m-1) при n, m > 0
# Найти F(3, 4)

@lru_cache(maxsize=None)
def F(n, m):
    if n == 0:
        return m
    if m == 0:
        return n
    return F(n - 1, m) + F(n, m - 1)

print(F(3, 4))

@lru_cache — инструмент при мемоизации рекурсии. Без него при большом n программа будет работать экспоненциально долго.

6. Краткий чек-лист

Выписать определение функции и значение, которое нужно найти.
Определить базовые случаи.
Построить цепочку вызовов (дерево или таблицу).
Вычислить значения снизу вверх.
Проверить результат через Python-код, если позволяет время.

7. Файлы решений

В папке Решение/ находятся примеры разобранных задач:

пример.md — шаблон ручного разбора рекуррентной функции (дерево вызовов + таблица значений).
.py-файлы — реализации функций на Python 3 с комментариями и проверкой ответа.

№16 Рекуррентные выражения