Задания № 16, 22 · ЕГЭ

Возвращаемое значение рекурсии

Как результат поднимается от базового случая к исходному вызову
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

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

\[F(n)=\begin{cases}b, & n=n_0\\G(n,F(n-1)), & n>n_0\end{cases}\]1

В этой записи \(b\) — результат базового случая, а \(G\) — действие, выполняемое после возврата из вложенного вызова. Важно: вызов, написанный глубже, должен сначала завершиться, и только затем выполняется выражение с его результатом. Поэтому дерево рекурсивных вызовов удобно читать снизу вверх.

№
Пример: факториал

Функция fact(n) возвращает \(n!\). Для вызова fact(4) цепочка выглядит так: fact(4) → fact(3) → fact(2) → fact(1). Базовый случай возвращает 1. Затем значения поднимаются обратно: fact(2) = 2 · 1 = 2, fact(3) = 3 · 2 = 6, fact(4) = 4 · 6 = 24. Исходный вызов получает значение 24.

Python
1def fact(n):
2    if n == 1:
3        return 1
4    return n * fact(n - 1)
!
Не путайте

Возвращаемое значение — не то же самое, что вывод на экран. return передаёт результат вызывающему коду, а print только отображает его и сам по себе не заменяет возвращаемое значение. Если написать print(fact(4)), на экран попадёт итог, но его передаёт наружу именно return внутри функции.

Проверьте себя

Что вернёт функция f(3), если f(1)=2, а для остальных аргументов выполняется f(n)=n+f(n-1)?

Главное за минуту

Главное

  • Сначала достигается базовый случай, затем результаты возвращаются к предыдущим вызовам.
  • Каждый уровень может обработать значение вложенного вызова и вернуть новый результат.
  • return передаёт значение, а print только выводит его на экран.