Рекурсия — это подход, при котором функция вызывает саму себя. В Go рекурсия работает, но с важными оговорками: здесь нет хвостовой оптимизации, и каждый рекурсивный вызов потребляет память на стеке. Это ограничение нужно учитывать при проектировании алгоритмов.
В этой статье разберём, как работает рекурсия в Go, сравним рекурсивный и итеративный подходы на двух классических задачах (факториал числа и числа Фибоначчи) и дадим практические советы по использованию рекурсии.
Как работает рекурсия в Go?
При вызове функции Go выделяет для неё фрейм на стеке горутины. При рекурсивном вызове каждый новый уровень создаёт новый фрейм. Когда функция завершается, её фрейм освобождается.
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1)
}
Вызов factorial(4) создаст на стеке:
factorial(4) → ждёт 4 * factorial(3) factorial(3) → ждёт 3 * factorial(2) factorial(2) → ждёт 2 * factorial(1) factorial(1) → возвращает 1
Глубина рекурсии — 4. Память на стеке выделяется под каждый фрейм.
Особенности рекурсии в Go
1. Нет хвостовой оптимизации
В некоторых языках (Scheme, Haskell, Scala) компилятор преобразует хвостовую рекурсию в цикл, чтобы не раздувать стек. В Go этого нет.
Пример хвостовой рекурсии (не оптимизируется):
func sumTail(n, acc int) int {
if n == 0 {
return acc
}
return sumTail(n-1, acc+n)
}
Хвостовой вызов здесь не оптимизируется — каждый вызов занимает место на стеке.
2. Стек горутины динамический, но с ограничением
Стек горутины в Go динамический: он начинается с 2 КБ и растет по мере необходимости. Но есть предел — около 1 ГБ для 64-битной архитектуры.
При sumTail(10000000, 0) программа отработает, потому что фрейм занимает мало места. Но если каждый фрейм содержит большие локальные переменные (например, структуры), переполнение наступит гораздо раньше.
3. Паника при переполнении
Если рекурсия исчерпает лимит стека, Go вызовет панику:
runtime: goroutine stack exceeds 1000000000-byte limit runtime: sp=0xc020071398 stack=[0xc020070000, 0xc040070000] fatal error: stack overflow
Сравнение подходов: задача Факториал
Начнём с простой задачи — вычисление факториала числа.
Факториал натурального числа n — это произведение всех натуральных чисел от 1 до n включительно. Обозначается как n! (читается как «эн факториал»).
Рекурсивная реализация:
func factRecursive(n int) int {
if n <= 1 {
return 1
}
return n * factRecursive(n-1)
}
Итеративная реализация:
func factIterative(n int) int {
result := 1
for i := 2; i <= n; i++ {
result *= i
}
return result
}
Сравнение:
| Подход | Время | Память | Риск stack overflow |
| Рекурсивный | O(n) | O(n) | Есть при очень больших n |
| Итеративный | О(n) | O(1) | Нет |
Факториал редко вычисляют для больших n из-за переполнения int64, но для демонстрации подходов задача подходит.
Сравнение подходов: задача Фибоначчи
Числа Фибоначчи — это числовая последовательность, в которой каждое последующее число равно сумме двух предыдущих.
Пример последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
Рекурсивная реализация
func fibRecursive(n int) int {
if n <= 1 {
return n
}
return fibRecursive(n-1) + fibRecursive(n-2)
}
Проблема: экспоненциальное количество вызовов. Для fibRecursive(40) будет ≈ 200 млн. вызовов. Глубина рекурсии небольшая (40), но время выполнения огромное.
Сложность: O(2ⁿ)
Итеративная реализация
func fibIterative(n int) int {
if n <= 1 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}
Сложность: O(n) по времени, O(1) по памяти. Нет риска переполнения стека.
Сравнение:
| Подход | Время | Память | Риск stack overflow |
| Рекурсивный | O(2ⁿ) | O(n) | Есть при больших n |
| Итеративный | О(n) | O(1) | Нет |
Вывод: для больших n итеративный подход предпочтительнее — он быстрее и не зависит от ограничения стека.
Когда рекурсия в Go оправдана?
Рекурсия хороша в задачах, где:
- Глубина рекурсии невелика — например, обход дерева глубиной до 1000 узлов.
- Код становится значительно проще — обход файловой системы, парсинг JSON/XML, алгоритмы на графах.
- Глубина заведомо мала — вы не можете предсказать глубину, но знаете, что она ограничена.
Пример безопасной рекурсии (задача 94 с Leetcode):
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
result := []int{}
inorder(root, &result)
return result
}
func inorder(node *TreeNode, result *[]int) {
if node == nil {
return
}
inorder(node.Left, result)
*result = append(*result, node.Val)
inorder(node.Right, result)
}
Глубина рекурсии здесь равна высоте дерева. Для сбалансированного дерева из миллиона узлов высота ≈ 20. Для вырожденного (все узлы в одной ветке) глубина может достигать количества узлов, но на практике такие деревья встречаются редко.
Когда рекурсия в Go опасна?
- Линейная рекурсия с очень большим n — если глубина рекурсии измеряется десятками миллионов, риск переполнения стека возрастает, особенно при больших фреймах.
- Рекурсия без базового случая — упадёт гарантированно.
- Рекурсия с большим потреблением на фрейм — структуры большого размера в параметрах увеличивают расход памяти.
Альтернативы: переписывание на итерацию, использование собственного стека ([]T), либо увеличение стека горутины (но это костыль).
Ключевой вывод
Рекурсия в Go работает и удобна для задач с небольшой глубиной (обход деревьев, разбор структур). Но из-за отсутствия хвостовой оптимизации каждый вызов занимает место на стеке.
Стек горутины динамический и может расширяться, но имеет предел, особенно если фреймы содержат много данных. Поэтому для линейных рекурсивных алгоритмов с потенциально большой глубиной лучше использовать итеративный подход или управлять стеком вручную.
А вы сталкивались с переполнением стека в Go? Какую задачу решали и как переписали? Делитесь в комментариях.
