Рекурсия

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

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

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

package main

import "fmt"

func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5)) // 120
}

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

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

Две ветки рекурсивной функции

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

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

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

Ветку, в которой функция завершается без рекурсии, называют базовым случаем. В factorial это if n == 0 { return 1 }: вызов 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(0), а потом разбирается сверху вниз. Виджет считает factorial(3), чтобы стопка поместилась на экране.

В самой глубокой точке factorial(5) на стеке лежат шесть записей вызовов factorial. Стек в Go растёт по мере надобности, но не бесконечно: на 64-битных системах его предел — 1 ГБ.

Хвостовые вызовы

Некоторые языки превращают в цикл рекурсивный вызов, стоящий последним действием функции, и стек не растёт. Такую замену называют оптимизацией хвостовых вызовов. Go её не делает: каждый рекурсивный вызов добавляет на стек новую запись.

Этот вопрос часто задают на собеседовании: «Есть ли в Go оптимизация хвостовых вызовов?» Ответ состоит из трёх частей:

• нет, Go её не делает;
• поэтому рекурсия расходует стек на каждом уровне;
• когда глубина может дойти до миллионов вызовов, вместо рекурсии пишут цикл.

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

Тот же факториал циклом:

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

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

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

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

fmt.Println(factorial(-1)) // ✗

fatal error: stack overflow

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

Главное

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