Рекурсия Python max, вопрос о sys.setrecursionlimit()

У меня есть один вопрос о sys.setrecursionlimit()

из документа python:

Установите максимальную глубину стека интерпретатора Python для ограничения. Этот предел предотвращает бесконечную рекурсию из-за C и сбой Python. Максимально возможный предел зависит от платформы. Пользователю может потребоваться установить лимит выше, когда у нее есть программа, требующая глубокой рекурсии и платформы, поддерживающей более высокий предел. Это должно быть сделано с осторожностью, потому что слишком высокий предел может привести к сбою.

Вот мой вопрос:

возьмем эту бесполезную рекурсивную функцию:

def rec(N):
     if N==0:
         return 1
     else:
         return rec(N-1);

теперь установите максимальную рекурсию на 100:

sys.setrecursionlimit(100)

Если я попробую rec(99) (100 рекурсивных вызовов), я получаю:

RuntimeError: maximum recursion depth exceeded

Для вычисления rec (99) мне нужно установить предел рекурсии на 105

Почему это так?

Ответ 1

Он плохо назван. Он должен сказать, что глубина стека, а не глубина рекурсии. Рекурсия подразумевает, что это тот же самый поток снова и снова, что он ограничивает. На самом деле у вас может быть фактический код, который имеет только 100 вызовов. Я бы не рекомендовал его, но мог. Они могут уйти от него, потому что в практическом мире, когда вы когда-либо сталкивались с этим сценарием, это рекурсия. Когда вы терпите крах из-за этого, видя слово "Рекурсия", вы сразу же узнаете, что искать, а не "Stack".

(Stack должен дать любому достойному программисту ту же подсказку, но пусть честно, ваш код просто разбился и вы хотите получить соответствующее сообщение об ошибке, правильно? 99.99999% времени это говорит вам, что именно вы испортили (вы пропустили свой базовый регистр для рекурсии.))

Ответ 2

Есть еще вызовы функций, которые должна выполняться во время выполнения Python, даже для вашей функции.

Ответ 3

Он основан на глубине стека TOTAL и не является действительно глубиной какой-либо конкретной отдельной функции. Вероятно, вы уже на глубине стека 5 при первом вызове rec().

Возьмем, например, 5 рекурсивных функций. Каждый из них выполняет 98 рекурсивных вызовов, причем последний из них относится к следующей рекурсивной функции. С лимитом рекурсии 100 вы действительно хотите разрешить каждой рекурсивной функции делать 99 вызовов для общей глубины ~ 500 вызовов? Нет, это может привести к сбою интерпретатора на этих глубинах.

Поэтому предел рекурсии - это максимальная глубина всех функций глобально, а не одна именованная функция.