Рекурсия: уменьшаем задачу и учитываем стек

Папка содержит файлы и вложенные папки. Чтобы посчитать файлы, нужно решить ту же задачу для каждого вложенного каталога. Рекурсия позволяет выразить это повторение, но программа должна знать, когда остановиться и почему каждый вызов приближает остановку.

Три вопроса к рекурсивной функции

Какой случай решается непосредственно? В каком смысле подзадача меньше исходной? Как из ответа подзадачи получить общий ответ? Если хотя бы одного ответа нет, выражение «функция вызывает себя» не объясняет алгоритм.

func Sum(a []int) int {
    if len(a) == 0 { return 0 }
    return a[0] + Sum(a[1:])
}

Пустой срез — базовый случай. Каждый вызов уменьшает длину на один. Предположим, сумма хвоста найдена правильно; тогда добавление первого элемента даёт сумму всего входа. Это индуктивное объяснение: база и переход от меньшего случая к большему.

Для [2,3,4] вызовы ждут ответы Sum([3,4]), Sum([4]), Sum([]). Возвраты идут обратно: 0,4,7,9. Вызов хранит место возврата и данные своего кадра. Даже без явного массива создаётся стек вызовов.

Почему рекурсия не всегда удобнее цикла

Такой Sum делает O(n) операций и использует O(n) глубины стека. Цикл с аккумулятором решил бы ту же задачу за O(n) времени и O(1) дополнительной памяти. Рост стека Go не означает, что доступна бесконечная рекурсия. Код не должен опираться на оптимизацию хвостового вызова как на гарантию языка.

Рекурсия полезна там, где сама структура ветвится: дерево, разбиение массива на части, перебор выбора. Но на длинной цепочке можно предпочесть собственный стек и цикл. Выбор зависит от максимальной глубины, удобства доказательства и допустимой памяти.

Ветвление меняет стоимость

Наивное вычисление Fibonacci вызывает две подзадачи: F(n−1) и F(n−2). При n=5 обе ветви многократно пересчитывают F(2). Глубина стека O(n), но число вызовов растёт экспоненциально. Одна оценка «есть рекурсия глубиной n» не описывает всё время выполнения.

Далее в динамическом программировании сохраним результаты повторяющихся подзадач. Сейчас нарисуйте дерево вызовов F(5) вручную и отметьте одинаковые узлы. Нужна не формальная красота дерева, а понимание источника повторной работы.

Рекурсивный перебор и восстановление состояния

Для генерации последовательностей a,b длины k на каждом шаге выбираем один символ, добавляем его в путь, вызываем функцию для следующей позиции, затем возвращаем путь к прежнему состоянию. Это backtracking: после исследования варианта отменяем временный выбор.

Когда сохраняете найденный путь из среза, делайте копию. Иначе несколько результатов могут разделять backing array и изменяться при следующем выборе. На k позициях существует 2^k результатов; даже идеальный алгоритм не выведет их за O(k), потому что размер ответа уже экспоненциален.

Самостоятельная практика

Напишите рекурсивный и циклический Sum. Для небольших целых чисел сравните ответы; договор ограничьте случаями без переполнения int. Затем реализуйте генератор всех слов из a,b длины 3. Ожидаются восемь разных слов, в том числе aaa и bbb. Не выдавайте общий backing array за восемь независимых результатов.

Критерии готовности: базовый случай срабатывает до доступа к элементу; подзадача уменьшается; время и глубина оценены отдельно; сохранённый результат не портится следующим вызовом. Практика — 40 минут.

Разбор

Для пустого Sum результат 0, а число дальнейших вызовов ноль. Генератор может использовать буфер фиксированной длины k, записывать символ по позиции и при достижении k создавать строку из буфера. Но хранение всех строк по-прежнему требует O(k·2^k) памяти результата. Учебное улучшение памяти не устраняет размер полного ответа.

В следующей главе рекурсия разделит массив на независимые половины, а слияние соберёт их обратно. Источники: MIT 6.006: учебные материалы, Go: slices.