Задание 11: рекурсия

Что такое рекурсия и зачем она нужна

Рекурсивные задачи часто кажутся сложными: функция вызывает саму себя, а в условии появляются степени, делители или последовательности. На самом деле ЕГЭ проверяет не магию, а умение увидеть два элемента: где вычисления останавливаются и как меняется аргумент. В этом разборе ты научишься читать рекурсивную функцию по шагам, составлять цепочку вызовов и быстро находить ответ без лишних вычислений.

Рекурсией называют способ решения задачи, при котором функция обращается к самой себе с другим значением аргумента. Каждый новый вызов должен приближать нас к остановке. Например, функция может уменьшать число на 1, делить его на 2 или переходить к предыдущему члену последовательности.

У любой корректной рекурсии есть базовый случай. Это условие, при котором функция уже знает ответ и не вызывает себя снова. Второй обязательный элемент — рекурсивный переход, то есть правило изменения аргумента.

Полезно сразу потренироваться на коротких примерах в бесплатной практике в личном кабинете: после нескольких цепочек вызовов структура рекурсии становится заметной.

Как читать рекурсивную функцию

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

Допустим, задана функция F(n): при n ≤ 1 она возвращает 1, а при n > 1 вычисляет F(n − 1) + n. Чтобы найти F(4), нельзя сразу подставить число в одну строку и запутаться. Нужно развернуть вызовы до базового случая:

\( F(4) = F(3) + 4 \)
\( F(3) = F(2) + 3 \)
\( F(2) = F(1) + 2 \)
\( F(1) = 1 \)

Теперь возвращаемся снизу вверх: F(2) = 3, F(3) = 6, F(4) = 10. Важно: сначала строится путь к остановке, а затем значения поднимаются обратно.

Разбираем пример полностью

Решим типичный пример. Пусть функция задана так: если n ≤ 2, то F(n) = 2n, иначе F(n) = F(n − 2) + F(n − 1). Найдём F(6). Здесь два предыдущих значения, поэтому вызовы образуют не одну цепочку, а небольшое дерево.

Начинаем с самых малых аргументов. Базовые значения: F(1) = 2 и F(2) = 4. Затем вычисляем последовательно F(3), F(4), F(5), F(6). Полная запись выглядит так:

\( F(3) = F(1) + F(2) = 2 + 4 = 6 \)
\( F(4) = F(2) + F(3) = 4 + 6 = 10 \)
\( F(5) = F(3) + F(4) = 6 + 10 = 16 \)
\( F(6) = F(4) + F(5) = 10 + 16 = 26 \)

Ответ: 26. Мы не раскрывали каждый повторный вызов заново, а сохранили уже найденные значения. Такой порядок особенно удобен, если рекурсия похожа на последовательность Фибоначчи.

Если в условии спрашивают не значение, а количество вызовов, считай сами обращения, включая самый первый вызов. Для больших аргументов лучше составлять таблицу, а не рисовать всё дерево.

Таблица и быстрый алгоритм решения

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

Шаг	Аргумент	Расчёт	Значение
1	1	2 × 1	2
2	2	2 × 2	4
3	3	F(1) + F(2)	6
4	4	F(2) + F(3)	10
5	5	F(3) + F(4)	16

Алгоритм решения простой: выпиши базовый случай, отметь изменение аргумента, найди значения от меньшего к большему и только потом подставь нужный аргумент. Если встречаются дроби, работай точно: например, 2⅓ лучше представить как 7⁄3, а ¾ не заменять приблизительным десятичным числом.

В личном кабинете можно решить ещё несколько задач и сравнить свой порядок вычислений с разбором.

Типичные ошибки на экзамене

Первая ошибка — пропустить базовый случай. Ученик продолжает раскрывать функцию, хотя значение уже известно. Всегда сначала проверяй условие остановки, особенно если оно записано как n ≥ 1 или n < 3.

Вторая ошибка — неверно изменить аргумент. Запись F(n − 1) означает уменьшение на единицу, а F(n ÷ 2) — деление аргумента, а не результата. При целочисленном делении уточняй, используется ли обычное деление или операция с целой частью.

Третья ошибка — считать только разные аргументы, когда спрашивают количество вызовов. В рекурсии F(n − 1) может встретиться несколько раз, и каждый вызов считается отдельно.

Наконец, не округляй промежуточные результаты. Формулы могут содержать √, степени, умножение × и деление. Оставляй точную форму до последнего шага.

Что запомнить

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

Если вызовов несколько, строй таблицу или небольшое дерево. Для вопросов о количестве вызовов внимательно учитывай повторения. Для вычислений со степенями и дробями сохраняй точные значения: 2² = 4, ¾ остаётся ¾, а √ сохраняется до финального ответа.

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. После каждого решения сверяй не только ответ, но и место, где появился первый неверный шаг.