Рекурсия: базовый случай, стек вызовов и примеры

Что такое рекурсия

Рекурсивная функция вызывает саму себя, чтобы решить меньшую версию той же задачи. У любой корректной рекурсии две части:

• Базовый случай — простейший вход, ответ на который известен сразу. Здесь вызовы прекращаются.
• Рекурсивный шаг — сведение задачи к меньшей и вызов функции для неё.

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

Как думать рекурсивно

Удобный приём — «поверить» функции. Не пытайтесь мысленно раскрутить все вызовы. Спросите себя:

1. Какой вход самый простой и какой у него ответ?
2. Если функция уже умеет решать задачу размера n − 1 (или половину, или поддерево), как получить ответ для n?
3. Каждый вызов точно приближается к базовому случаю?

Пример 1: факториал

n! = n × (n − 1)!, а 0! = 1.

def factorial(n):
    if n == 0:          # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный шаг

Стек вызовов наглядно

Каждый вызов функции кладёт в стек вызовов свой кадр: аргументы, локальные переменные и место возврата. Для factorial(3):

factorial(3)  ждёт 3 * factorial(2)
  factorial(2)  ждёт 2 * factorial(1)
    factorial(1)  ждёт 1 * factorial(0)
      factorial(0)  возвращает 1
    factorial(1)  возвращает 1
  factorial(2)  возвращает 2
factorial(3)  возвращает 6

Сначала стек растёт вниз до базового случая, потом раскручивается обратно, и каждый кадр доделывает своё умножение.

Пример 2: обход дерева

Деревья рекурсивны по природе: у узла есть дети, которые сами являются деревьями. Поэтому рекурсия здесь естественнее циклов.

def tree_sum(node):
    if node is None:
        return 0
    return node.value + sum(tree_sum(child) for child in node.children)

Так же обходят файловую систему, DOM-дерево, вложенные комментарии и меню.

Пример 3: перестановки

Задача: вывести все перестановки списка. Рекурсивная мысль: выбираем первый элемент всеми способами, а остальное переставляем рекурсивно.

def permutations(items):
    if len(items) <= 1:
        return [items]
    result = []
    for i, first in enumerate(items):
        rest = items[:i] + items[i + 1:]
        for perm in permutations(rest):
            result.append([first] + perm)
    return result

Это пример перебора с возвратом (backtracking): на тех же идеях решаются судоку, задача о ферзях и генерация комбинаций.

Переполнение стека

Стек вызовов ограничен. Если рекурсия слишком глубокая, программа падает с ошибкой stack overflow (в Python — RecursionError).

Причины:

• Нет базового случая или он недостижим, например factorial(-1).
• Слишком большая глубина — рекурсия на тысячи и миллионы уровней, например обход длинного связного списка.

Что делать:

• Проверять входные данные и базовый случай.
• Переписать алгоритм на цикл или явный стек (список, в который вы сами кладёте задачи).
• Использовать подход «разделяй пополам», чтобы глубина была O(log n), а не O(n).

Хвостовая рекурсия

Рекурсия называется хвостовой, если рекурсивный вызов — последнее действие функции и результат возвращается как есть:

def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)

Некоторые компиляторы и языки (например, Scheme, часто — функциональные языки) умеют превращать такой вызов в цикл, и стек не растёт. Python и большинство реализаций JavaScript этого не делают, поэтому в них хвостовая форма от переполнения не спасает — нужен цикл.

Рекурсия или цикл