Почему не работает setrecursionlimit

Question

from functools import lru_cache
import sys

sys.setrecursionlimit(10000)

@lru_cache(None)
def f(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n > 2:
        return n * f(n - 1) - f(n - 2)


print(f(2024) + f(2020) - f(2019))

При попытке выполнения показывается ошибка, и указано, что строка была выполнена 996 раз, хотя лимит стоит на 10000.

  File "D:\PyCharm\pythonProject\practice.py", line 307, in <module>
    print(f(2024) + f(2020) - f(2019))
          ^^^^^^^
  File "D:\PyCharm\pythonProject\practice.py", line 304, in f
    return n * f(n - 1) - f(n - 2)
               ^^^^^^^^
  File "D:\PyCharm\pythonProject\practice.py", line 304, in f
    return n * f(n - 1) - f(n - 2)
               ^^^^^^^^
  File "D:\PyCharm\pythonProject\practice.py", line 304, in f
    return n * f(n - 1) - f(n - 2)
               ^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Answer 1

Previous line repeated 996 more times

Это означает, что при выводе трейса ошибки Питон сэкономил экраны вывода и не стал повторять одну и ту же строку вывода 999 раз, а вывел её только три раза и написал "ну и ещё 996 раз такая же строка должна была вывестись, но мне лениво было".

К глубине собственно рекурсии эта надпись имеет косвенное отношение. Поскольку в строке с print вызова функция вызывается 3 раза, а внутри функции каждый раз рекурсивно ещё по 2 раза, да ещё lru_cache сверху навешен, то сложно понять, сколько всего было вызовов. Кстати, глубина рекурсии тратится не только на собственно рекурсию, а на любой вызов функции в принципе. А декоратор - это тоже дополнительный вызов функции.

В общем, попробуйте убрать декоратор lru_cache и посмотрите, что получится. Возможно, надпись будет уже гораздо ближе к выставленному вами лимиту.

P.S. А если вы хотите просто посчитать результат, то лимит рекурсии трогать не нужно, а нужно просто "прогреть кэш". Лимит рекурсии превышается из-за использования рекурсии и из-за того, что кэш всё время промахивается. Нужно просто наполнить кэш заранее и тогда промахов не будет и рекурсии фактически тоже не будет, значения будут браться сразу из кэша:

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n > 2:
        return n * f(n - 1) - f(n - 2)

# "прогрев" кэша
for i in range(2025):
    f(i)

# само вычисление
print(f(2024) + f(2020) - f(2019))

Вообще этот вопрос тут много раз уже поднимался на разные лады.

Answer 2

Так здесь n просто в глубокий минус уходит. Нужна ещё одна проверка на отрицательность.

if n < 0:
   return 0

Answer 3

Этот код хорошо работает в Питоне 3.11 и сломан в 3.12, 3.13. Его починят в 3.14.

Сообщение об ошибке вводит в заблуждение, когда говорит что в стеке только вызовы функции f. На функцию f надет декоратор @lru_cache, который каждый вызов f оборачивает в вызов другой функции-обёртки. В действительности, стек выглядит как-то так:

...
вызов wrapper_f(2024)
вызов         f(2024)
вызов wrapper_f(2023)
вызов         f(2023)
вызов wrapper_f(2022)
вызов         f(2022)
...

Здесь wrapper_f – обёртка, которая проверяет наличие аргумента в кэше. Если он там есть, возвращается значение из кэша. Если нет (а его нет в нашем примере), вызывается f.

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

wrapper_f написана на C, в отличие от f, которую вы написали на Питоне. В версии 3.12 было сделано усовершенствование:

https://docs.python.org/3/whatsnew/3.12.html#sys:

...

sys.setrecursionlimit() и sys.getrecursionlimit(). Предел глубины рекурсии теперь применяется только к коду на Питоне. Встроенные функции не используют его, они защищены другим механизмом, который не позволяет рекурсии обрушить виртуальную машину.

Это хорошее изменение. Раньше, когда вы ограничивали глубину рекурсии каким-то пределом, в примере из вопроса ошибка случалась на в два раза меньшей глубине стека, чем этот предел. Именно из-за скрытых вызовов wrapper_f. Это вызывало вопросы и было исправлено. Теперь если лимит тысяча, то код на Питоне может использовать всю тысячу.

К сожалению, тот "другой механизм" состоит в том что количество вложенных вызовов функций написанных на C ограничены константой и не зависят от установки sys.setrecursionlimit(). Вы не можете им управлять. И именно количество вложенных вызовов функций на C останавливает работу вашего кода.

Что можно сделать?

Не использовать Питон 3.12, 3.13. Если вам не нужны самые-самые новые изменения в языке, оставайтесь на 3.11 и ждите выхода 3.14.
Не использовать глубокую рекурсию. В любом случае вызов sys.setrecursionlimit() не сделает ваш стек очень глубоким. Даже на Питоне 3.11, где этого бага нет, если вы передадите большое число в качестве лимита, это лимит вам не гарантирован.

БЛОГ НА HUSL

Почему не работает setrecursionlimit

Ответы (3 шт):