Рекурсия

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

Чтобы понять рекурсию, надо сначала понять рекурсию. Шутка старая, но это буквально определение.

Матрёшка: открываешь, а внутри матрёшка поменьше. Открываешь её - ещё меньше. И так пока не дойдёшь до самой маленькой, которая уже не открывается. Вот эта неоткрывающаяся и есть самое главное.

Забыл самую маленькую - функция зовёт себя бесконечно, стек переполняется, программа падает. Поэтому сначала пиши, где остановиться. Потом уже - как спускаться глубже.

В паттерне Декоратор матрёшка тоже встречается, но про другое: там про вложенность обёрток вокруг одного объекта, здесь - про глубину вызова и момент остановки.

Основы рекурсии

Каждая рекурсивная функция должна иметь:

1. Базовый случай - когда рекурсия останавливается
2. Рекурсивный шаг - вызов себя с уменьшенной задачей

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 и растёт динамически, но бесконечная рекурсия всё равно упадёт.

Стрелки вниз - это ты открываешь матрёшки одну за другой. Стрелки вверх - складываешь их обратно, и только тут появляется результат.

Примеры рекурсии

Числа Фибоначчи

// Наивная реализация - O(2^n), очень медленно!
func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

// С мемоизацией через [map](./07-maps.md) - 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)
    }
}

Рекурсия 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
}

<ComparisonTable data={{ headers: ["", "Рекурсия", "Итерация"], rows: [ ["Читаемость", "Для деревьев, графов - понятнее", "Для линейных задач - проще"], ["Память", "O(n) стек вызовов", "O(1)"], ["Скорость", "Overhead на вызовы", "Обычно быстрее"], ["Когда", "Деревья, графы, вложенные структуры", "Массивы, числа, линейные задачи"] ] }} />

Типичные ошибки

// ОШИБКА 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) // будет считать миллиарды лет

Первые две ошибки - про одно и то же: самой маленькой матрёшки либо нет вовсе, либо спуск пролетает мимо неё.