Статья Автор: Деникина Н.В., Деникин А.В.

Разности и шаг рекурсии

Сокращаем хвост рекурсии

Если в условии стоит разность значений функции, часто достаточно раскрыть два шага. Ниже два реальных задания с исходными аргументами.

(Досрочный ЕГЭ-2025) 

Сложение при каждом шаге
F(n) = 1, если n ≤ 5; F(n) = n + F(n − 2), если n > 5.

Вычислите F(2126) − F(2122).

Два раскрытия
F(2126) = 2126 + F(2124) F(2124) = 2124 + F(2122)

В разности F(2126) − F(2122) общий хвост исчезает.

2126 + 2124 = 4250

Ответ: 4250



Шаг сразу на 2
F(n) = 1, если n ≤ 2; F(n) = n · F(n − 2), если n > 2.

Вычислите (F(2027) − F(2025)) / F(2023).

Шаг 2023 → 2025 → 2027
F(2025) = 2025 · F(2023) F(2027) = 2027 · 2025 · F(2023)

Одинаковое F(2023) сокращается.

2025 · (2027 − 1) = 4 102 650

Ответ: 4102650



Не заменяйте исходные аргументы маленькими числами. Обратите внимание: шаг n−1, n−2 или n−7 определяет, сколько раз нужно раскрыть рекурсию.
Печать