Рекурсия

Откройте матрёшку — внутри окажется такая же, только поменьше. Откройте её, и там ещё одна. Так продолжается до самой маленькой, которая уже не открывается. Потом матрёшки собирают в обратном порядке: самую маленькую закрывают в предпоследней, ту — в следующей, и так до самой большой.

Некоторые задачи устроены так же: внутри задачи сидит та же задача, только поменьше. Факториал числа n — произведение всех целых чисел от 1 до n. Его определяют двумя правилами:

• факториал нуля равен 1;
• факториал n равен n, умноженному на факториал n - 1.

Метод на C# повторяет это определение дословно, вызывая сам себя:

Console.WriteLine(Factorial(5)); // 120

int Factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}

Приём, при котором метод вызывает сам себя, называют рекурсией, а такой метод — рекурсивным.

Две части рекурсивного метода

В рекурсивном методе всегда две части. Разберём каждую.

Базовый случай

Ветку, в которой метод завершается без нового вызова, называют базовым случаем. В Factorial это if (n == 0): вызов Factorial(0) сразу возвращает 1. Это самая маленькая матрёшка, которая уже не открывается.

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

Вызов самого себя

Строка return n * Factorial(n - 1); вызывает тот же метод с аргументом на единицу меньше. Factorial(5) ждёт результата Factorial(4), тот ждёт Factorial(3), и так до Factorial(0).

Затем результаты идут по цепочке обратно, как собираются матрёшки:

1. Factorial(0) возвращает 1.
2. Factorial(1) возвращает 1 * 1, то есть 1.
3. Factorial(2) возвращает 2 * 1, то есть 2.
4. Factorial(3) возвращает 3 * 2, то есть 6.
5. Factorial(4) возвращает 4 * 6, то есть 24.
6. Factorial(5) возвращает 5 * 24, то есть 120.

Стек вызовов

Каждый вызов получает собственный параметр n, поэтому Factorial(5), Factorial(4) и остальные вызовы друг другу не мешают. Пока вызов не завершился, среда выполнения хранит для него рамку: его параметры и место, куда вернуть результат.

Рамки незавершённых вызовов лежат стопкой, которую называют стеком вызовов:

• новый вызов кладёт свою рамку сверху;
• завершённый вызов снимает верхнюю рамку.

Нажимайте «Следующий шаг» и следите, как стопка рамок растёт до Factorial(0), а потом разбирается сверху вниз. Виджет считает Factorial(3), чтобы стопка поместилась на экране.

Код, который стоит в методе после рекурсивного вызова, выполняется, только когда вложенный вызов вернётся. Поэтому умножения в Factorial идут в обратном порядке: первым считается 1 * 1 в Factorial(1), последним — 5 * 24 в самом первом вызове, Factorial(5).

Здесь аналогия с матрёшками перестаёт работать. Матрёшки все разные, а метод в программе один. Для каждого вызова отдельно хранятся только его данные: параметр n и место, куда вернуть результат.

Глубина рекурсии

Стек вызовов не бесконечен. Каждый вызов, который ещё не вернулся, занимает в нём место, и при слишком глубокой рекурсии место кончается. Тогда возникает исключение StackOverflowException.

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

Об этом часто спрашивают на собеседовании: «Можно ли перехватить StackOverflowException?» Ответ — нет. Поэтому рекурсию пишут так, чтобы её глубина заведомо оставалась небольшой.

Цикл вместо рекурсии

Тот же факториал можно посчитать циклом:

Console.WriteLine(FactorialLoop(5)); // 120

int FactorialLoop(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
    {
        result = result * i;
    }
    return result;
}

Цикл не вызывает новых методов: переменные result и i меняются на месте, и стопка вызовов не растёт, сколько бы ни было шагов. Когда глубина рекурсии заранее неизвестна или может оказаться большой, вместо рекурсии пишут цикл.

Частая ошибка

Рекурсивный метод вызвали с аргументом, для которого базовый случай недостижим:

Console.WriteLine(Factorial(-1)); // ✗

Stack overflow.

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

Проверяйте, что базовый случай достижим из любого допустимого аргумента, а недопустимые аргументы отсекайте до рекурсивного вызова. Например, проверьте n >= 0 в if и вызывайте Factorial(n) только внутри этой ветки.

Главное

• Рекурсивный метод вызывает сам себя, и ему нужен достижимый базовый случай: ветка, в которой он завершается без нового вызова.
• Каждый вызов получает свои параметры и ждёт, пока вернётся вложенный; код после рекурсивного вызова выполняется на обратном пути.
• Слишком глубокая рекурсия переполняет стек вызовов, а StackOverflowException нельзя перехватить: программа завершается. Если глубина может оказаться большой, пишут цикл.