Рекурсия и почему Python её (не) любят 🌀
Если на собеседовании вас просят написать факториал или числа Фибоначчи через рекурсию — пишите. Но если вы часто ее используете в реальности... Да, рекурсия концептуальна красива, математически элегантна, но если увлечься, можно уронить прод и забить всю оперативку фреймами стека.
Разбираем, что происходит под капотом и почему Python, в отличие от функциональных языков, рекурсию недолюбливает.
1️⃣ Цена вопроса: стек вызовов Каждый вызов функции — это не бесплатно. Это создание нового стек-фрейма в памяти. В этом фрейме хранятся локальные переменные и адрес возврата. Представьте матрешку, где каждая следующая кукла весит столько же, сколько предыдущая. В Python этот "вес" ложится на оперативку. Цикл while или for использует один блок памяти. Рекурсия жрет память линейно (или экспоненциально) пропорционально глубине вызова.
2️⃣ Почему нет хвостовой оптимизации В языках типа Haskell или C++ компилятор умный. Если рекурсивный вызов — последнее действие в функции (хвостовая рекурсия), он подменяет его на обычный прыжок (GOTO), не создавая новый фрейм. Это называется Tail Call Optimization (TCO).
В Python TCO нет и не будет. Гвидо ван Россум (BDFL) принципиально против TCO в Python. Аргумент простой: «Мы хотим видеть полные трейсбеки ошибок». Если схлопнуть стек, вы никогда не узнаете, на каком именно витке рекурсии всё упало. Поэтому лимит в 1000 вызовов (дефолтный) — это не баг, а предохранитель от переполнения стека. Можно ли его увеличить через sys.setrecursionlimit? Можно. Но если вам это понадобилось, 99% вероятность, что вы ошиблись с архитектурой.
3️⃣ Когда рекурсия — зло, а когда — необходимость? ❌ Линейные структуры (например, списки): Вычисление факториала, чисел Фибоначчи или обход плоского списка. Итеративный цикл while/for всегда будет быстрее и экономичнее по памяти (O(1) памяти против O(N)). ✅ Разветвленные структуры (деревья, графы, вложенные dict): Парсинг JSON, обход файловой системы, DOM-дерева или алгоритмы типа Divide and Conquer (QuickSort, MergeSort). Здесь рекурсия снижает когнитивную нагрузку и делает код читаемым.
4️⃣ Лекарство от тормозов: @lru_cache Классический пример глупости — вычисление Фибоначчи "в лоб". Сложность O(2^n). Это значит, что для вычисления 50-го числа программа умрет раньше, чем закончит. Решение — Мемоизация. Декоратор @functools.lru_cache кэширует результаты вызовов. Если функция уже считалась с этим аргументом, Python просто достанет готовое значение из хэш-таблицы. Это превращает экспоненциальный ужас в линейную сложность O(N).
Итого: Python — это не Haskell и не Lisp. Здесь рекурсия — это гражданин второго сорта. Используйте её для деревьев и графов, но для всего остального есть циклы.
