Рекуррентное мышление: база, переход и стек вызовов

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

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

У рекурсивного решения всегда должны быть две части:

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

Пример с факториалом

Факториал числа n — это произведение чисел от 1 до n.

def factorial(n):
    if n == 0:
        return 1

    return n * factorial(n - 1)

print(factorial(5))

Базовый случай — n == 0. Без него функция вызывала бы себя бесконечно.

Как читать рекурсию

Не пытайтесь раскрывать сразу все вызовы в голове. Сначала проверьте базовый случай. Затем убедитесь, что каждый шаг приближает к нему. После этого разберите маленький пример: factorial(3) вызывает factorial(2), затем factorial(1), затем factorial(0).

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

Многие рекурсивные задачи можно решить циклом. Например, сумму чисел от 1 до n проще записать через for. Рекурсия полезнее там, где структура задачи сама разветвляется: дерево вариантов, обход файлов, перебор ходов, разбор выражения.

Частые ошибки

Главная ошибка — забыть базовый случай или не уменьшать задачу. Вторая ошибка — использовать рекурсию там, где обычный цикл проще и надежнее. В Python есть ограничение глубины рекурсии, поэтому очень длинные цепочки вызовов лучше решать циклом.

Для школьника рекурсия важна не только как прием кодирования. Она учит видеть задачу через повторяющуюся структуру: решить маленькую часть и передать похожую работу следующему вызову.