Рекурсия в Python работает за счёт того, что функция вызывает саму себя для решения задачи. 2 Сложные задачи разбиваются на более простые подзадачи одного и того же типа. 2 Каждый вызов функции работает над своей «меньшей» версией задачи до тех пор, пока не достигается предельно простой случай, который может быть решён напрямую. 2
Рекурсивная функция обычно имеет две ключевые составляющие: 2
В момент, когда функция вызывает сама себя, действие «материнской» функции приостанавливается — и начинается выполнение «дочерней». 3 Так как рано или поздно программа должна вернуться к «материнской» функции, нужно сохранить данные о её работе. 3 Для этого существует стек вызовов. 3
При каждом новом вызове функции на вершине стека оказывается новый блок. 3 Он начинает работать, остальные же в это время ничего не делают и просто хранят данные. 3 Так происходит, пока рекурсия не доходит до базового случая. 3
У стека всегда есть максимально допустимый размер. 3 Например, в Python он равен 1000 вызовов. 3 Если максимум достигнут, а пытаются положить в стек ещё одну функцию, происходит ошибка «Переполнение стека». 3