Рекурсия

Некоторые задачи удобно описывать через самих себя. Факториал числа n — это произведение всех чисел от 1 до n: факториал 5 равен 1 * 2 * 3 * 4 * 5, то есть 120. Его можно определить двумя правилами:

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

Функция на Swift повторяет это определение слово в слово, вызывая саму себя:

func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}

print(factorial(5)) // 120

Вернёмся к комбайну и посмотрим, как он считает factorial(5):

1. Комбайн factorial получил 5, но сразу ответа не знает.
2. Он ставит рядом такой же комбайн, отдаёт ему 4 и ждёт результат, чтобы умножить его на 5.
3. Второй комбайн так же передаёт работу третьему с числом 3, и так до комбайна, который получил 0.
4. Последний сразу отвечает 1, никого не вызывая.

Здесь картинка с комбайнами неточна. Настоящие комбайны могут работать одновременно, а из вызовов функции в каждый момент выполняется только самый новый. Остальные ждут, пока он вернёт результат.

Два вида веток

Рекурсия — это вызов функцией самой себя. Компилятор такой вызов разрешает: имя функции видно внутри её собственного тела. У рекурсивной функции есть ветки двух видов.

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

Ветку, в которой функция завершается без нового вызова, называют базовым случаем. В factorial это if n == 0 { return 1 }: вызов factorial(0) сразу возвращает 1.

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

Рекурсивный шаг

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

Потом результаты возвращаются вверх по цепочке, и каждый вызов умножает полученное на своё n:

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.

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

Функцию, которая складывает числа от 1 до n, написали без базового случая:

func sumTo(_ n: Int) -> Int {
    return n + sumTo(n - 1) // ✗
}

warning: function call causes an infinite recursion

Программа компилируется, но с предупреждением: у функции нет ни одной ветки без нового вызова. Предупреждение не останавливает сборку, но отнеситесь к нему как к ошибке: такая функция не вернёт ответ ни при каком аргументе. Добавьте базовый случай перед рекурсивным шагом: if n == 0 { return 0 }.

Главное

• Рекурсия — вызов функцией самой себя; у рекурсивной функции есть базовый случай и рекурсивный шаг.
• Базовый случай завершает функцию без нового вызова, и каждый новый вызов должен приближать аргумент к нему.
• Результаты возвращаются вверх по цепочке: factorial(0) отдаёт 1, и каждый вызов умножает полученное на своё n.
• Функцию совсем без базового случая компилятор замечает и предупреждает: function call causes an infinite recursion.