Рекурсия в программировании: примеры и подводные камни

Рекурсия — один из самых элегантных и одновременно опасных приёмов в программировании. Понимание её принципов открывает доступ к множеству алгоритмов: от обхода деревьев до динамического программирования.

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

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

Любая корректная рекурсия состоит из двух обязательных частей:

• Базовый случай (base case) — условие, при котором функция возвращает результат сразу, не вызывая себя снова.
• Рекурсивный шаг (recursive step) — вызов функции с изменёнными аргументами, которые приближают её к базовому случаю.

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

Формула и основные правила

Общий шаблон рекурсивной функции:

function f(n):
    if базовый_случай(n):
        return простой_результат
    return комбинация(f(меньшее_n))

Классический пример — факториал:

n! = 1,            если n = 0 или n = 1
n! = n * (n-1)!,   если n > 1

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

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2),  при n >= 2

Правила, которые помогают писать корректную рекурсию:

1. Сначала проверяйте базовый случай, потом делайте рекурсивный вызов.
2. Аргументы должны строго приближаться к базовому случаю.
3. Оценивайте глубину стека: типичный лимит — около 1000 вызовов в Python, 10000-50000 в C++.
4. Если в рекурсии повторяются одинаковые подзадачи — добавляйте мемоизацию.

Пример

Посчитаем факториал числа 5 на Python:

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

print(factorial(5))  # 120

Пошаговое раскрытие вызовов:

Каждый вызов «откладывается» в стек, пока не достигнут базовый случай. Затем стек начинает разворачиваться: возвраты идут в обратном порядке.

Более сложный пример — наивные числа Фибоначчи:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

При n = 5 функция совершит 15 вызовов, при n = 30 — уже больше миллиона. Дерево рекурсии содержит огромное количество повторов: fib(3) вычисляется заново снова и снова. Решение — мемоизация:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Сравнение количества вызовов:

Разница экспоненциальна. Рекурсия без оптимизации легко превращается из изящного решения в катастрофу по производительности.

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

1. Отсутствие или недостижимый базовый случай. Например, factorial(-1) в коде выше уйдёт в бесконечную рекурсию, потому что n будет уменьшаться, но никогда не станет равным 1. Проверяйте границы и валидируйте вход.

2. Неправильное изменение аргумента. Если вместо f(n-1) написать f(n) или передавать неизменённый объект (список, словарь), рекурсия не будет приближаться к базе. Особенно опасно при работе со структурами данных по ссылке.

3. Игнорирование экспоненциального роста. Наивная рекурсия с двумя ветвями (как Фибоначчи или перебор подмножеств) почти всегда требует мемоизации или перехода к итеративному динамическому программированию.

4. Переполнение стека на больших глубинах. Обход списка из 100 000 элементов через рекурсию упадёт в Python почти гарантированно. В таких случаях используйте итерацию, увеличивайте лимит через sys.setrecursionlimit (с осторожностью) или применяйте «хвостовую» переписку через цикл.

Когда стоит обратиться за помощью

Рекурсия — тема, которая хорошо понимается только через практику: написание собственного кода, отрисовку дерева вызовов, отладку шаг за шагом. Если задача по обходу дерева, перебору вариантов или динамическому программированию вызывает ступор, попробуйте сначала разобрать готовый разобранный пример с похожей структурой, а затем повторить решение самостоятельно.

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