Рекурсия в Python: от матрешки до стека вызовов. Полный гид для новичков / Хабр

Рекурсия. Введение.

Многие новички воспринимают рекурсию как некий «высший пилотаж» или магию, доступную только после прочтения томов по Computer Science. На деле это просто один из способов организации логики, когда функция вызывает саму себя.

Как это выглядит в жизни?

Самый точный пример — матрешка. Чтобы добраться до самой маленькой фигурки, вам нужно выполнить одно и то же действие: «открыть текущую матрешку». Вы повторяете этот шаг снова и снова, пока не достигнете финала (базового случая).

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

В чем главная суть?

Рекурсия строится на принципе «Разделяй и властвуй». Мы не пытаемся решить огромную задачу целиком. Вместо этого мы:

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

Зачем это нужно разработчику?

Есть структуры данных и задачи, которые по своей природе иерархичны (самоподобны). Пытаться обрабатывать их обычными циклами for или while — значит писать громоздкий и плохо читаемый код.

Рекурсия незаменима в трех случаях:

Обход файловых систем: Папка может содержать файлы и другие папки. Структура вложенности повторяется.
Работа с вебом и данными: DOM-дерево в браузере (HTML) или сложные JSON-ответы — это деревья, где каждый узел может содержать такие же узлы.
Алгоритмы на деревьях и графах: Поиск кратчайшего пути, сортировка (например, QuickSort) или обход связей в соцсетях.

Если задача разбивается на подзадачи, которые выглядят точно так же, как основная — значит, здесь место рекурсии. Посмотрим, как реализовать это на Python и не «уронить» систему.

Анатомия рекурсии

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

1. Базовый случай (Условие выхода)

Это точка остановки. Условие, при котором функция перестает вызывать саму себя и начинает возвращать конкретное значение. Без него программа будет плодить вызовы до тех пор, пока у системы не закончится память.

2. Рекурсивный шаг (Движение к выходу)

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

«Плохая» рекурсия: RecursionError

Рассмотрим классическую ошибку — отсутствие условия выхода.

def call_myself():
    return call_myself()

call_myself()

В этом коде нет проверки, когда нужно остановиться. Если вы запустите его в Python, вы не получите «вечный двигатель». Интерпретатор выдаст ошибку:
RecursionError: maximum recursion depth exceeded.

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

«Хорошая» рекурсия: Сумма чисел

Разберем рабочий пример: функцию для подсчета суммы чисел от n до 1. Например, для n=3 сумма будет 3 + 2 + 1 = 6.

def sum_to_one(n):
    # 1. Базовый случай
    if n <= 1:
        return n
    
    # 2. Рекурсивный шаг
    return n + sum_to_one(n - 1)

print(sum_to_one(3)) # Результат: 6

Как это работает на практике:

Мы вызываем sum_to_one(3).
Программа проверяет: 3 <= 1? Нет.
Она запоминает 3 + ... и запускает sum_to_one(2).
Для 2 всё повторяется: запоминается 2 + ... и запускается sum_to_one(1).
На sum_to_one(1) срабатывает базовый случай. Функция просто возвращает 1.
Теперь накопленная цепочка «схлопывается»: 3 + 2 + 1.

Важный нюанс: Обратите внимание на n - 1. Это и есть движение к выходу. Если бы мы передавали просто n, функция вызывала бы себя для тройки бесконечно. Мы же каждый раз уменьшаем задачу, пока она не станет элементарной (равной единице).

Как это работает «под капотом»: Стек вызовов

Чтобы понять рекурсию, нужно перестать думать о ней как о «цикле» и начать думать как о стеке вызовов (Call Stack). Это структура данных в оперативной памяти, которая работает по принципу «последним пришел — первым ушел» (LIFO).

Что такое фрейм стека?

Каждый раз, когда вы вызываете любую функцию в Python, интерпретатор создает в памяти фрейм (запись). В этом фрейме хранится:

Локальные переменные функции.
Текущая строка кода, которая выполняется.
Адрес возврата (куда отдать результат, когда функция закончит работу).

Когда функция вызывает другую функцию (или саму себя), текущий фрейм «замораживается» и кладется в стек, а сверху создается новый.

Визуализация: Вычисляем factorial(3)

Факториал числа — это произведение всех чисел от 1 до . Код выглядит так:

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

fact(3)

Вот что происходит в памяти пошагово:

Этап 1: Наполнение стека (Спуск)

Вызов fact(3): Python создает фрейм для . Чтобы вернуть результат, ему нужно вычислить 3 * fact(2). Выполнение замирает, мы ждем ответа от fact(2).
Вызов fact(2): Поверх первого фрейма кладется второй для . Он ждет результат 2 * fact(1).
Вызов fact(1): Создается третий фрейм. Здесь срабатывает базовый случай. Функция просто возвращает 1.

Этап 2: Схлопывание стека (Подъем)
Теперь, когда у нас есть конкретное число, фреймы начинают закрываться один за другим:

fact(1) возвращает 1 во фрейм fact(2). Фрейм fact(1) удаляется из памяти.
fact(2) теперь может закончить расчет: 2 * 1 = 2. Он возвращает 2 во фрейм fact(3) и удаляется.
fact(3) завершает финальный расчет: 3 * 2 = 6. Это итоговый результат.

Почему рекурсия «ест» память?

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

В рекурсии каждый шаг — это новый блок памяти (фрейм).

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

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

Ограничения Python: Почему нельзя вызвать функцию миллион раз?

Если вы попробуете использовать рекурсию для обхода списка из 10 000 элементов, вы почти наверняка столкнетесь с «кирпичом» в виде RecursionError. Это не случайный баг, а осознанное ограничение интерпретатора.

Лимит рекурсии: зачем он нужен?

В Python по умолчанию установлен лимит на глубину стека — обычно это 1000 вызовов.

Это «защита от дурака». Поскольку каждый вызов создает новый фрейм в памяти, бесконечная рекурсия могла бы легко поглотить всю оперативную память и привести к падению всей операционной системы (Stack Overflow). Python предпочитает «убить» одну программу, чем позволить ей обрушить систему.

Как управлять лимитом через sys

Вы можете проверить текущий лимит и даже изменить его:

import sys

print(sys.getrecursionlimit())  # Обычно 1000

sys.setrecursionlimit(2000)     # Увеличиваем лимит

Опасно ли это? Да. Увеличение лимита не делает стек бесконечным. Оно просто отодвигает черту. Если вы поставите лимит в 100 000 и ваша рекурсия до него дойдет, программа может вылететь с критической ошибкой Segmentation fault (жесткое падение интерпретатора без внятных объяснений), потому что закончится память, выделенная под стек на уровне C.

Почему в Python нет оптимизации хвостовой рекурсии (TCO)?

В некоторых языках (например, Haskell, Elixir или даже JavaScript в некоторых реализациях) существует Tail Call Optimization (TCO). Это механизм, который понимает: если рекурсивный вызов — это самое последнее действие в функции, то старый фрейм можно не хранить, а просто заменить его новым. В теории это позволяет делать бесконечную рекурсию без расхода памяти.

В Python этого нет, и вот почему (позиция Гвидо ван Россума, создателя языка):

Читаемость стектрейса: Гвидо считает, что отладка важнее оптимизации. Если оптимизировать хвост, из traceback (отчета об ошибках) исчезнут промежуточные шаги, и вы не увидите всю цепочку вызовов.
Динамическая природа Python: В Python можно подменить функцию прямо на лету. Это делает автоматическую оптимизацию хвостовых вызовов крайне сложной для реализации в самом интерпретаторе.
Идеология: Python — это императивный язык. Гвидо неоднократно заявлял, что для итераций нужно использовать циклы, а не пытаться превратить Python в функциональный язык.

Вердикт: Если ваша задача требует 5000+ рекурсивных вызовов — в Python это четкий сигнал, что нужно переписать алгоритм на обычный цикл while или использовать стек на базе списка (list.append/pop).

Рекурсия vs Итерация: что выбрать?

Математически доказано, что любую рекурсию можно заменить циклом, и наоборот. Однако на практике выбор между ними — это всегда компромисс между красотой кода и производительностью системы.

Когда лучше использовать циклы (for, while)

Итерация — это базовый инструмент Python. Она работает «плоско» и предсказуемо.

Линейные задачи: Если вам нужно просто пройтись по списку, суммировать числа или найти элемент, цикл всегда будет быстрее и безопаснее.
Экономия памяти: Цикл использует фиксированный объем памяти. Сколько бы миллионов итераций вы ни сделали, новые фреймы в стеке не создаются.
Производительность: В Python вызов функции — это относительно «дорогая» операция. Простой переход к следующей итерации цикла выполняется быстрее.

Когда лучше использовать рекурсию

Рекурсия выигрывает там, где данные имеют иерархическую или вложенную структуру.

Деревья и ветвление: Представьте, что вам нужно обойти все папки на диске. В каждой папке может быть еще пять папок, а в них — еще по три. Написать это через циклы можно, но вам придется вручную создавать «стек» (список), чтобы запоминать, в какую ветку вы еще не зашли. Рекурсия делает это автоматически и элегантно.
Читаемость: Рекурсивный код часто выглядит как математическое определение задачи. Он короче и его легче понять коллегам (если они знают базу рекурсии).
Разделяй и властвуй: Алгоритмы вроде быстрой сортировки (QuickSort) или обхода графов пишутся на рекурсии в несколько строк, тогда как их итеративные аналоги могут занимать десятки строк сложной логики.

Сводная таблица

Характеристика	Рекурсия	Итерация (Циклы)
Код	Элегантный, часто короче.	Бывает громоздким при вложенности.
Память	Затратно: каждый вызов ест память стека.	Экономно: использует одну и ту же память.
Скорость	Медленнее из-за накладных расходов на вызов функций.	Максимально возможная для Python.
Ошибки	`RecursionError` (переполнение стека).	Бесконечный цикл (просто зависание).

Главное правило:

Если структура данных, с которой вы работаете, фрактальна (часть структуры похожа на целую структуру — например, папка в папке или ветка в дереве), используйте рекурсию.

Если вы просто обрабатываете последовательность (список, строка, диапазон чисел), используйте цикл.

В следующем разделе мы увидим, как «медленную» рекурсию можно разогнать до скоростей цикла с помощью мемоизации.

Продвинутый уровень: Динамическое программирование и Мемоизация

Рекурсия может быть не только элегантной, но и ужасающе неэффективной, если использовать её «в лоб». Классический пример — вычисление чисел Фибоначчи.

Ловушка Фибоначчи

Числа Фибоначчи определяются просто: каждое следующее число — это сумма двух предыдущих.
Код так и просится:

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

Попробуйте запустить fib(35), а затем fib(40). Вы заметите, как компьютер начинает «задумываться». На fib(100) программа не закончит расчет и до тепловой смерти Вселенной.

В чем проблема? В избыточности. Чтобы вычислить fib(5), функция вызывает fib(4) и fib(3). Но fib(4) в свою очередь снова вызывает fib(3) и fib(2).
В итоге одно и то же значение fib(3) мы вычисляем десятки раз, fib(2) — сотни. Это называется экспоненциальной сложностью.

Мемоизация: учим функцию «запоминать»

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

Можно написать свой декоратор для этого:

def memoize(func):
    cache = {}
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper

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

print(fib(100)) # Мгновенный результат!

Магия одной строки: functools.lru_cache

В Python этот механизм уже встроен и работает эффективнее самодельных словарей. Декоратор lru_cache (Least Recently Used) кэширует результаты и следит за тем, чтобы кэш не раздувался до бесконечности.

from functools import lru_cache

@lru_cache(maxsize=None) # maxsize=None означает бесконечный кэш
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))

Что изменилось?
С этой строчкой сложность алгоритма упала с экспоненциальной до линейной. Теперь fib(100) выполняется за доли миллисекунды, потому что Python делает ровно 100 вычислений, а всё остальное берет из памяти.

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

Практические примеры: где без рекурсии больно

Теория — это хорошо, но рекурсию ценят за решение задач, которые «плоскими» циклами описываются либо слишком сложно, либо нечитаемо.

1. Суммирование вложенных списков

Представьте, что вам пришел JSON или список с глубокой и непредсказуемой вложенностью: [1, [2, [3, 4], 5], 6]. Вам нужно найти сумму всех чисел. Обычный цикл for обработает только верхний уровень.

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

def deep_sum(lst):
    total = 0
    for item in lst:
        if isinstance(item, list):
            total += deep_sum(item)  # Рекурсия для вложенного списка
        else:
            total += item
    return total

data = [1, [2, [3, 4], 5], 6]
print(deep_sum(data))  # Результат: 21

2. Обход файловой системы

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

Код ниже имитирует работу стандартной функции os.walk, но в упрощенном виде:

import os

def list_all_files(path):
    # Проходим по всем объектам в текущей папке
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        
        if os.path.isdir(full_path):
            # Если это папка — заходим внутрь (рекурсия)
            list_all_files(full_path)
        else:
            # Если файл — просто выводим путь
            print(f"Файл: {full_path}")

# list_all_files('my_projects')

Попробуйте написать это на циклах while, и вам придется вручную создавать очередь (queue) для запоминания путей, в которые еще нужно зайти. Рекурсия делает это неяв��о через стек вызовов.

3. Почему деревья — это стандарт для JSON и HTML

Почти всё, с чем мы работаем в вебе, имеет древовидную структуру:

HTML/DOM: Тег <div> содержит <p>, который содержит <span>. Это дерево.
JSON: Объект содержит ключи, значениями которых могут быть другие объекты.

Почему здесь важна рекурсия? Потому что глубина вложенности заранее неизвестна. Программист, пишущий парсер JSON, не знает, сколько уровней вложил туда другой разработчик. Рекурсия позволяет написать универсальный алгоритм: он просто «спускается» на уровень ниже до тех пор, пока не встретит конечные данные (строку или число).

Вердикт: Если ваша структура данных «ветвится» — рекурсия будет самым естественным способом работы с ней. В остальных случаях лучше остаться с циклами.

Заключение и чек-лист

Рекурсия — это мощный инструмент, который делает код чище там, где данные имеют сложную структуру. Но в Python это всегда компромисс между красотой и производительностью. Чтобы не запутаться, используйте этот короткий чек-лист.

3 «золотых» правила любой рекурсии

Если вы пишете рекурсивную функцию, проверьте её по этим пунктам:

Базовый случай (Условие выхода): Описано ли поведение функции для самых простых входных данных (0, 1, пустой список)? Это ваш предохранитель от бесконечного цикла.
Движение к финалу: Стал ли аргумент функции на следующем шаге «проще»? Если вы вычисляете факториал , следующий вызов должен быть . Если вы обходите список, передавайте его часть без первого элемента.
Возврат результата: Не забываете ли вы слово return перед рекурсивным вызовом? Типичная ошибка новичка — вызвать функцию саму из себя, но не передать её результат «наверх» по стеку.

Когда стоит остановиться и переписать всё на цикл

Рекурсия — не серебряная пуля. Переходите на for или while, если:

Глубина стека > 1000: Если ваша задача требует обработки 5000 вложенных элементов, Python «выкинет флаг» RecursionError.
Память в дефиците: Каждый рекурсивный шаг — это новый фрейм. Если функция оперирует тяжелыми объектами, вы быстро исчерпаете RAM.
Задача линейна: Обход обычного массива, поиск максимального числа или фильтрация списка всегда эффективнее и понятнее через цикл.
Производительность критична: Если функция вызывается миллионы раз в секунду, накладные расходы на создание новых фреймов стека в Python станут «бутылочным горлышком».

Что изучить дальше?

Если вы освоили базу, вот куда стоит копать дальше:

Визуализация: Обязательно прогоните свои примеры через Python Tutor. Это лучший способ увидеть, как «дышит» стек вызовов в реальном времени.
Алгоритмы: Посмотрите, как рекурсия используется в «Быстрой сортировке» (QuickSort) и «Сортировке слиянием» (Merge Sort).
Функциональное программирование: Почитайте про чистые функции и то, почему в языках вроде Haskell рекурсия — основной способ циклической обработки.
Декораторы: Изучите functools.lru_cache более глубоко — это спасет вас во многих задачах на динамическое программирование.

Анонсы новых статей, полезные материалы, а так же если в процессе у вас возникнут сложности, обсудить их или задать вопрос по этой статье можно в моём Telegram-сообществе. Смело заходите, если что-то пойдет не так, — постараемся разобраться вместе.

Главное помнить: Рекурсия должна упрощать код, а не усложнять его отладку. Если вы полчаса пытаетесь понять, почему функция возвращает None вместо числа — возможно, пришло время заменить её простым циклом.

Рекурсия в Python: от матрешки до стека вызовов. Полный гид для новичков