Не работает lru_cache(None)

Question

Не работает lru_cache(None)

Рейтинг: 0Ответов: 1Опубликовано: 23.01.2023

Хоть я и выставил неограниченное количество рекурсии, но программа все равно заканчивается на ошибке RecursionError: maximum recursion depth exceeded

from functools import *
@lru_cache(None)


def foo(n):
    if n >= 10000:
        return n
    if (n < 10000) and (n % 2 == 0):
        return 1 + foo(n / 2)
    if (n < 10000) and (n % 2 == 1):
        return (n ** 2) + foo(n + 2)
    
for i in 9, 192:
    foo(i)

python

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Если в foo подаётся нечётное число, то она начинает рекурсивно ходить по одной и той же ветке кода:

    if (n < 10000) and (n % 2 == 1):
        return (n ** 2) + foo(n + 2)

Потому что n + 2 - это тоже нечётное число в случае, если n было нечётное. Перебираются все нечётные числа подряд, начиная с начального:

Таким образом, в этой ветке будет совершено (10000 - n - 1) / 2 рекурсивных итераций. Для n = 9 с которого вы начинаете, это будет 4995, не каждый интерпретатор питона может выдержать такую степень рекурсии, даже если вы и повысите её лимит.

Причём, повышать уровень рекурсии нужно выше этого числа, там есть и другие накладные расходы.

P.S. С чётной веткой у вас тоже смешно. Если напечатать n с которым происходит обращение к функции, то получится:

192
96.0
48.0
24.0
12.0
6.0
3.0
5.0
7.0
9.0
11.0
13.0
15.0
...

То есть сначала чётное число, которого, конечно же, нет в кэше, потом чётные числа с плавающей точкой, которых опять же нет в кэше, а дальше числа нечётные, но не целые, как было при первом прогоне с n = 9, а с плавающей точкой. Для кэша целые числа и числа с плавающей точкой - это разные числа!

В итоге кэш у вас вообще ни разу не сработал, это можно проверить по статистике использования кэша:

print(foo.cache_info())
# CacheInfo(hits=0, misses=10003, maxsize=None, currsize=10003)

Значение hits=0 говорит нам о том, что значение из кэша ни разу не было использовано.

И да, я надеюсь вы понимаете, что for i in 9, 192: - это цикл всего по двум числам: 9 и 192? Это кортеж. Вот если бы вы сделали такой цикл for i in range(9, 192):, то кэш мог бы быть использован и довольно эффективно. А сейчас у вас что есть кэш, что нет - абсолютно никакой разницы, он совсем не используется.

Не работает lru_cache(None)

Ответы