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

Рекурсивная функция обычно имеет две ключевые составляющие: 2

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

В момент, когда функция вызывает сама себя, действие «материнской» функции приостанавливается — и начинается выполнение «дочерней». 3 Так как рано или поздно программа должна вернуться к «материнской» функции, нужно сохранить данные о её работе. 3 Для этого существует стек вызовов. 3

При каждом новом вызове функции на вершине стека оказывается новый блок. 3 Он начинает работать, остальные же в это время ничего не делают и просто хранят данные. 3 Так происходит, пока рекурсия не доходит до базового случая. 3

У стека всегда есть максимально допустимый размер. 3 Например, в Python он равен 1000 вызовов. 3 Если максимум достигнут, а пытаются положить в стек ещё одну функцию, происходит ошибка «Переполнение стека». 3