Рекурсия
Рекурсия - это когда функция вызывает саму себя. Звучит как магия, но на практике - мощный инструмент для задач с вложенной структурой.
Чтобы понять рекурсию, надо сначала понять рекурсию. Шутка старая, но это буквально определение.
Матрёшка: открываешь, а внутри матрёшка поменьше. Открываешь её - ещё меньше. И так пока не дойдёшь до самой маленькой, которая уже не открывается. Вот эта неоткрывающаяся и есть самое главное.
| В жизни | В коде |
|---|---|
| матрёшка внутри матрёшки | функция вызывает саму себя |
| самая маленькая, цельная | базовый случай |
| стопка открытых половинок на столе | стек вызовов |
| половинки кончились, стол завален | stack overflow |
Забыл самую маленькую - функция зовёт себя бесконечно, стек переполняется, программа падает. Поэтому сначала пиши, где остановиться. Потом уже - как спускаться глубже.
В паттерне Декоратор матрёшка тоже встречается, но про другое: там про вложенность обёрток вокруг одного объекта, здесь - про глубину вызова и момент остановки.
Основы рекурсии
Каждая рекурсивная функция должна иметь:
- Базовый случай - когда рекурсия останавливается
- Рекурсивный шаг - вызов себя с уменьшенной задачей
func factorial(n int) int {
// Базовый случай
if n <= 1 {
return 1
}
// Рекурсивный шаг
return n * factorial(n-1)
}
fmt.Println(factorial(5)) // 120 = 5 * 4 * 3 * 2 * 1
Что происходит в памяти
factorial(5)
→ 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 ← базовый случай
← 2 * 1 = 2
← 3 * 2 = 6
← 4 * 6 = 24
← 5 * 24 = 120
Каждый вызов создаёт новый фрейм на стеке. В Go стек начинается с ~2-8 KB и растёт динамически (почему так - разберём в уроке про горутины), но бесконечная рекурсия всё равно упадёт.
Стрелки вниз - это ты открываешь матрёшки одну за другой. Стрелки вверх - складываешь их обратно, и только тут появляется результат.
⚠️ Stack overflow
Без базового случая рекурсия бесконечна →
runtime: goroutine stack exceeds .... Всегда проверяй, что базовый случай достижим.
Примеры рекурсии
Числа Фибоначчи
Вторая версия ниже кеширует результаты в map.
// Наивная реализация - O(2^n), очень медленно!
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}
// С мемоизацией через map - O(n)
func fibMemo(n int, cache map[int]int) int {
if n <= 1 {
return n
}
if val, ok := cache[n]; ok {
return val
}
cache[n] = fibMemo(n-1, cache) + fibMemo(n-2, cache)
return cache[n]
}
Обход дерева файлов
func listFiles(path string, indent int) {
entries, err := os.ReadDir(path)
if err != nil {
return
}
prefix := strings.Repeat(" ", indent)
for _, entry := range entries {
fmt.Printf("%s%s\n", prefix, entry.Name())
if entry.IsDir() {
listFiles(filepath.Join(path, entry.Name()), indent+1)
}
}
}
// Использование
listFiles(".", 0)
Обход вложенного JSON
func printJSON(data any, indent int) {
prefix := strings.Repeat(" ", indent)
switch v := data.(type) {
case map[string]any:
for key, val := range v {
fmt.Printf("%s%s:\n", prefix, key)
printJSON(val, indent+1)
}
case []any:
for i, val := range v {
fmt.Printf("%s[%d]:\n", prefix, i)
printJSON(val, indent+1)
}
default:
fmt.Printf("%s%v\n", prefix, v)
}
}
Бинарный поиск (рекурсивный)
func binarySearch(sorted []int, target, lo, hi int) int {
if lo > hi {
return -1 // не найден
}
mid := (lo + hi) / 2
switch {
case sorted[mid] == target:
return mid
case sorted[mid] < target:
return binarySearch(sorted, target, mid+1, hi)
default:
return binarySearch(sorted, target, lo, mid-1)
}
}
Хвостовая рекурсия
Рекурсия называется хвостовой, если рекурсивный вызов - последнее действие функции и после него ничего не вычисляется:
// Хвостовая: результат копится в аккумуляторе acc
func factorialTail(n, acc int) int {
if n <= 1 {
return acc
}
return factorialTail(n-1, n*acc) // после вызова ничего не делаем
}
// Не хвостовая: после вызова ещё нужно умножить на n
// return n * factorialRec(n-1)
Во многих функциональных языках компилятор превращает хвостовую рекурсию в цикл (это называют TCO, tail call optimization), и стек не растёт. Go так не делает: каждый вызов, даже хвостовой, получает новый фрейм на стеке. Поэтому для глубокой рекурсии в Go аккумулятор не спасает - такие функции переписывают обычным циклом.
Рекурсия vs Итерация
Любую рекурсию можно переписать через цикл:
// Рекурсия
func factorialRec(n int) int {
if n <= 1 {
return 1
}
return n * factorialRec(n-1)
}
// Итерация - быстрее, не использует стек
func factorialIter(n int) int {
result := 1
for i := 2; i <= n; i++ {
result *= i
}
return result
}
| Рекурсия | Итерация | |
|---|---|---|
| Читаемость | Для деревьев, графов - понятнее | Для линейных задач - проще |
| Память | O(n) стек вызовов | O(1) |
| Скорость | Overhead на вызовы | Обычно быстрее |
| Когда | Деревья, графы, вложенные структуры | Массивы, числа, линейные задачи |
ℹ️ Правило
Используй рекурсию, когда структура данных рекурсивна (дерево, граф, вложенный JSON). Для линейных задач (factorial, fibonacci) - итерация лучше.
Типичные ошибки
// ОШИБКА 1: забыли базовый случай
func infinite(n int) int {
return n + infinite(n-1) // никогда не остановится!
}
// ОШИБКА 2: базовый случай недостижим
func badFib(n int) int {
if n == 0 { return 0 }
return badFib(n-1) + badFib(n-2) // при n=1 вызовет badFib(-1) → бесконечность
}
// ОШИБКА 3: наивная рекурсия без мемоизации
fib(50) // десятки миллиардов вызовов: около минуты; fib(90) уже не дождёшься
Первые две ошибки - про одно и то же: самой маленькой матрёшки либо нет вовсе, либо спуск пролетает мимо неё.
Мини-задание
- Запусти рекурсию без базового случая и прочитай сообщение о переполнении стека. Найди в нём, до какой глубины дошло
- Посчитай факториал рекурсивно и циклом, сравни через
go test -bench . -benchmem - Посчитай число Фибоначчи наивной рекурсией для n=40 и замерь время. Добавь кеш (map) и замерь снова
- Посмотри, оптимизирует ли Go хвостовую рекурсию: собери с
-gcflags='-m'и поищиinlining call - Обойди дерево каталогов рекурсивно, потом перепиши через
filepath.WalkDirи сравни объём кода