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

Базовый случай рекурсии

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

Базовый случай рекурсии — это условие, при выполнении которого алгоритм перестаёт вызывать сам себя и сразу возвращает результат. Он необходим, чтобы рекурсивный алгоритм завершался, а не выполнялся бесконечно.

Базовый случай рекурсииСлово «базовый» означает исходный, начальный: это простейший случай, для которого ответ известен непосредственно.
Условие остановки рекурсивных вызовов, при котором дальнейшее обращение алгоритма к самому себе не выполняется. Для всех остальных входных данных используется рекурсивный случай — действие, включающее новый вызов алгоритма с изменёнными данными.

Как распознать базовый случай

В программе базовый случай обычно проверяется в условной конструкции if. Если условие истинно, функция возвращает готовый ответ или выполняет действие без нового рекурсивного вызова. Во время каждого следующего вызова данные должны приближаться к базовому случаю; иначе глубина рекурсии может стать чрезмерной.

\[f(n)=\begin{cases}b, & \text{если выполнено базовое условие},\\g(n,f(h(n))), & \text{иначе}. \end{cases}\]
№
Пример: факториал

Для факториала базовым случаем является \(n=0\): \(0!=1\). При \(n>0\) функция вызывает себя для меньшего числа: \(n!=n\cdot(n-1)!\). Поэтому вычисление для \(3\) проходит так: \(3\cdot2\cdot1\cdot0!\), после чего возвращается \(1\) и вызовы завершаются.

Python
1def factorial(n):
2    if n == 0:          # базовый случай
3        return 1
4    return n * factorial(n - 1)
!
Не путайте с рекурсивным случаем

Базовый случай не вызывает функцию повторно. Строка return n * factorial(n - 1) — рекурсивный случай. Если проверка базового случая отсутствует или параметр не приближается к нему, алгоритм не остановится. Базовый случай также не обязан иметь значение \(0\): это может быть \(n=1\), пустая строка, пустой список или другое простейшее состояние.

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

Какое условие является базовым случаем в функции f(n): if n <= 1: return 1; return n * f(n - 1)?

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

Главное

  • Базовый случай — условие, при котором рекурсивные вызовы прекращаются.
  • Он возвращает известный результат без обращения функции к самой себе.
  • Параметры в рекурсивном случае должны приближаться к базовому случаю.