Рекурсия

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

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

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

В жизниВ коде
матрёшка внутри матрёшкифункция вызывает саму себя
самая маленькая, цельнаябазовый случай
стопка открытых половинок на столестек вызовов
половинки кончились, стол заваленstack overflow

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

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

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

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

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

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

⚠️ 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 и сравни объём кода

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.