Какие ограничения есть у рекурсии в Python?

1️⃣ Как кратко ответить

Рекурсия в Python ограничена глубиной стека вызовов, которая по умолчанию составляет 1000. Это предотвращает переполнение стека и падение программы. Для обхода этого ограничения можно использовать модуль sys для изменения лимита, но это может привести к нестабильности. Рекурсия также может быть менее эффективной по сравнению с итерацией из-за накладных расходов на вызовы функций.

2️⃣ Подробное объяснение темы

Ограничение глубины стека вызовов

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

import sys
​
# Получение текущего лимита рекурсии
current_limit = sys.getrecursionlimit()
print("Текущий лимит рекурсии:", current_limit)
​
# Установка нового лимита рекурсии
sys.setrecursionlimit(1500)
print("Новый лимит рекурсии:", sys.getrecursionlimit())

• import sys: Импортирует модуль sys, который предоставляет доступ к некоторым переменным и функциям, взаимодействующим с интерпретатором Python.
• sys.getrecursionlimit(): Возвращает текущий лимит глубины рекурсии.
• sys.setrecursionlimit(1500): Устанавливает новый лимит глубины рекурсии. Это может быть полезно для задач, требующих глубокой рекурсии, но следует использовать с осторожностью, так как слишком высокий лимит может привести к нестабильности программы.

Накладные расходы

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

Пример: Факториал

Рассмотрим пример вычисления факториала числа с использованием рекурсии:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
​
print(factorial(5))  # Вывод: 120

• def factorial(n): Определяет функцию factorial, которая принимает один аргумент n.
• if n == 0: Базовый случай рекурсии. Если n равно 0, возвращается 1, так как факториал 0 равен 1.
• return n * factorial(n - 1): Рекурсивный случай. Умножает n на факториал n-1, вызывая функцию factorial с аргументом n-1.