Рекурсия: функция, вызывающая саму себя

Урок раскрывает рекурсию — приём, когда функция вызывает саму себя, — на классических примерах факториала и чисел Фибоначчи.

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

Что такое рекурсия

Представьте, что вы стоите в длинной очереди и хотите узнать, какой вы по счёту. Можно спросить человека впереди: «Какой ты по счёту?» Тот, чтобы ответить, спросит того, кто перед ним, и так далее — до самого первого, который точно знает: «Я первый». Затем ответы возвращаются назад: первый говорит «1», второй прибавляет себя и говорит «2», и волна докатывается до вас. Это и есть рекурсия: задача решается через ту же задачу, но поменьше, пока не дойдём до самого простого случая, ответ на который известен сразу.

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

Два обязательных элемента рекурсии

У любой правильной рекурсии есть две части, и обе критически важны:

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

Без базового случая функция вызывала бы себя бесконечно и программа аварийно завершилась бы (переполнение стека). Базовый случай — это аварийный тормоз. Запомните: каждый рекурсивный вызов должен приближать к базовому случаю.

Классика: факториал

Факториал числа n (записывается n!) — это произведение всех чисел от 1 до n: 5! = 1·2·3·4·5 = 120. Заметьте рекурсивную природу: n! = n · (n−1)!. То есть факториал n выражается через факториал меньшего числа. А базовый случай: 1! = 1 (дальше дробить некуда).

function Factorial(n: integer): integer;
begin
  if n <= 1 then
    Result := 1                     // базовый случай
  else
    Result := n * Factorial(n - 1); // рекурсивный случай
end;

begin
  writeln(Factorial(5));   // 120
end.

Проследим, как считается Factorial(5): чтобы вычислить его, нужно 5 * Factorial(4), для этого — 4 * Factorial(3), и так до Factorial(1), которое сразу равно 1. Затем результаты перемножаются на обратном пути: 1 → 2 → 6 → 24 → 120. Запустите аналог на Python:

def factorial(n):
    if n <= 1:
        return 1                    # базовый случай
    else:
        return n * factorial(n - 1) # рекурсивный случай

print(factorial(5))

Вывод:

Как работают вложенные вызовы

Каждый вызов функции живёт в своей «комнате» памяти со своими параметрами. Factorial(5) приостанавливается и ждёт, пока Factorial(4) вернёт ответ; тот ждёт Factorial(3), и так далее. Это похоже на матрёшку: чтобы собрать большую, нужно сначала собрать все меньшие внутри. Когда самая маленькая (базовый случай) готова, ответы возвращаются наружу слой за слоем. Понимание этого «спуска и подъёма» — ключ к рекурсии.

Числа Фибоначчи

Ещё один классический пример — последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13... Каждое число равно сумме двух предыдущих. Рекурсивное определение почти дословно повторяет правило: F(n) = F(n−1) + F(n−2), а базовые случаи — F(1) = 1 и F(2) = 1.

def fib(n):
    if n <= 2:
        return 1                       # базовые случаи F(1)=F(2)=1
    else:
        return fib(n - 1) + fib(n - 2) # рекурсивный случай

for i in range(1, 9):
    print(fib(i), end=' ')
print()

Вывод:

1 1 2 3 5 8 13 21

Здесь видно, как красиво рекурсия выражает определение «через себя». Правда, у этого варианта есть скрытая беда: он много раз пересчитывает одни и те же значения, поэтому для больших n работает медленно. Это нормальный повод узнать, что не всякую задачу стоит решать рекурсивно.

Рекурсия против цикла

Почти любую рекурсию можно переписать обычным циклом, и наоборот. Тот же факториал прекрасно считается циклом for (мы это делали в разделе про циклы). Когда что выбирать?

Цикл — обычно быстрее и экономнее по памяти; хорош для простого повторения и накопления.
Рекурсия — элегантнее для задач, которые естественно дробятся на подобные подзадачи: обход дерева, перебор вариантов, фракталы, задачи вида «ханойские башни».

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

Попробуй сам

Напишите рекурсивную функцию Summa(n), которая считает сумму чисел от 1 до n (1+2+...+n). Идея: Summa(n) = n + Summa(n−1), базовый случай Summa(1) = 1. Проверьте на Python:

def summa(n):
    if n <= 1:
        return 1
    else:
        return n + summa(n - 1)

print('Сумма 1..10 =', summa(10))

Вывод:

Сумма 1..10 = 55

Частые ошибки

Нет базового случая. Без условия остановки функция вызывает себя бесконечно — программа падает с переполнением стека. Базовый случай обязателен.
Рекурсивный вызов не уменьшает задачу. Если вызывать Factorial(n) вместо Factorial(n - 1), до базового случая никогда не дойти. Каждый вызов должен упрощать задачу.
Забыли вернуть результат. В рекурсивной ветке нужно именно вернуть n * Factorial(n - 1), а не просто вызвать функцию, выбросив её результат.
Применяют рекурсию там, где проще цикл. Глубокая рекурсия для простого счёта тратит память зря; иногда цикл уместнее.

Итоги

Рекурсия — функция, вызывающая саму себя для решения уменьшенной версии задачи.
Обязательны базовый случай (точка остановки) и рекурсивный случай (сведение к меньшей задаче).
Каждый вызов хранит свои данные; ответы возвращаются «изнутри наружу», как в матрёшке.
Факториал (n! = n·(n−1)!) и числа Фибоначчи — хрестоматийные примеры рекурсии.
Рекурсию почти всегда можно заменить циклом; выбирают по удобству и эффективности.