Почему не работает 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))

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

БЛОГ НА HUSL

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

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