Рекурсивные алгоритмы: принципы и вычисление в задании 16 ЕГЭ

Коротко о главном

Рекурсия — это способ описания алгоритма, при котором функция вызывает саму себя с изменёнными (обычно уменьшенными) параметрами. Любой рекурсивный алгоритм состоит из двух частей: базового случая (условие остановки, ответ известен сразу) и рекурсивного случая (переход к более простой подзадаче). В задании 16 чаще всего просят вычислить значение функции при конкретном $n$ или найти $n$, при котором результат удовлетворяет условию. Ключевой навык — уметь "развернуть" рекурсию в цепочку вызовов и посчитать значения снизу вверх (от базового случая к исходному).

Определения и формулы/правила

Понятие	Пояснение
Базовый случай	Условие, при котором функция возвращает значение без дальнейших вызовов, например $F(0)=1$
Рекурсивный случай	Вызов функции с меньшим аргументом: $F(n)=F(n-1)+n$
Дерево вызовов	Схема всех вызовов функции, показывает порядок вычислений
Глубина рекурсии	Число вложенных вызовов до достижения базового случая
Раскрутка (снизу вверх)	Метод: сначала находим $F(0)$, $F(1)$, ..., затем нужное $F(n)$

Общий вид линейной рекурсии: $$F(n) = \begin{cases} c, & n = n_0 \\ g(n, F(n-1)), & n > n_0 \end{cases}$$

При двух рекурсивных вызовах (как в числах Фибоначчи): $$F(n) = F(n-1) + F(n-2), \quad F(1)=F(2)=1$$

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

Как применять

Пример 1. Дана функция:

function F(n)
  if n = 0 then F := 1
  else F := F(n-1) * 2
end

Найти $F(4)$.

Раскрутка: $F(0)=1$, $F(1)=2$, $F(2)=4$, $F(3)=8$, $F(4)=16$.

Пример 2. Функция с двумя ветвями:

function F(n)
  if n <= 1 then F := n
  else F := F(n-1) + F(n-2)
end

Найти $F(6)$.

$F(0)=0$, $F(1)=1$, $F(2)=1$, $F(3)=2$, $F(4)=3$, $F(5)=5$, $F(6)=8$.

Пример 3. Найти наименьшее $n$, при котором $F(n) > 100$, если $F(n) = F(n-1) + n$, $F(1)=1$.

$F(1)=1$, $F(2)=3$, $F(3)=6$, $F(4)=10$, $F(5)=15$, $F(6)=21$, $F(7)=28$, $F(8)=36$, $F(9)=45$, $F(10)=55$, $F(11)=66$, $F(12)=78$, $F(13)=91$, $F(14)=105$. Ответ: $n=14$.

Типичные ошибки

• Забывают базовый случай и пытаются вычислять "от начала", а не строить цепочку снизу вверх.
• Путают порядок операций в формуле: например, считают $F(n-1)\cdot 2$ как $F(n\cdot 2 - 1)$.
• Неверно определяют, какая ветвь if срабатывает при конкретном $n$ (особенно при условиях вида "чётное/нечётное" или "больше/меньше некоторого значения").
• При двух рекурсивных вызовах (как в Фибоначчи) забывают учесть оба слагаемых или путают индексы.
• Ошибаются в промежуточных вычислениях из-за длинной цепочки — рекомендуется оформлять таблицу значений по шагам.
• Не проверяют, требуется ли найти значение функции или значение аргумента, при котором выполняется условие — это разные типы вопросов.

Где встречается на экзамене

Тема входит в задание 16 (ранее № 11) и иногда пересекается с заданиями на анализ алгоритмов (задание 17, 23). Требуется либо вычислить значение рекурсивной функции для заданного $n$, либо найти минимальное/максимальное $n$, удовлетворяющее условию на результат. Иногда рекурсия задаётся не явной формулой, а псевдокодом или блок-схемой — важно уметь переводить такую запись в математическую зависимость.