Рекурсия

Когда функция вызывает саму себя, чтобы решить меньшую версию той же задачи

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

К концу вы сможете:

объяснить, что такое рекурсивная функция,
отличать базовый случай от рекурсивного случая,
проследить, как стек вызовов растёт, а потом сворачивается,
читать классические примеры, такие как факториал и Фибоначчи,
решать, когда рекурсия понятнее цикла.

1. Что такое рекурсия?

Представьте набор матрёшек. Вы открываете большую куклу и находите внутри меньшую. Открываете её — и находите ещё меньшую. Вы продолжаете, пока не дойдёте до самой крошечной куколки, которая вообще не открывается. Эта последняя куколка — место, где вы останавливаетесь.

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

В теме Функции в C++ вы узнали, что функция может вызывать другую функцию. Вот что удивительно: функции разрешено вызывать саму себя. Вот и вся рекурсия.

У рекурсивного решения две задачи: знать, когда остановиться, и знать, как сделать задачу меньше на пути к остановке.

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

У каждой хорошей рекурсивной функции есть ровно две части:

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

Посмотрите на обратный отсчёт от числа до нуля:

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n < 0) {          // БАЗОВЫЙ СЛУЧАЙ: делать больше нечего
        return;
    }
    cout << n << " ";     // немного работы
    countdown(n - 1);     // РЕКУРСИВНЫЙ СЛУЧАЙ: меньшая задача
}

int main() {
    countdown(3);
    return 0;
}

Ожидаемый вывод:

3 2 1 0

Обратите внимание, что каждый вызов передаёт n - 1. Число всё уменьшается: 3, потом 2, потом 1, потом 0, потом -1. Когда оно наконец достигает -1, срабатывает базовый случай return; и цепочка вызовов останавливается.

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

Рекурсия