«Максимальная глубина рекурсии» при использовании lru_cache

Я ва от functools импорта lru_cache @lru_cache ( MaxSize = None ) четкости п ( п : ИНТ ) -> INT : если ( п == 0 ): возвращение 1 возвращение п + е ( п - 1 ) ### MAIN ### print ( f ( 1000 )) для вычисления рекурсивной функции с использованием lru_cache. Вот упрощенная версия:

RecursionError: maximum recursion depth exceeded in comparison

Он работает хорошо, когда я запускаю f (100), но с f (1000) я получаю:

>>> f(400)
80201
>>> f(800)  # will stop recursing at 400
320401
>>> f(1000) # will stop recursing at 800
500501

Одним из решений является вычисление таблицы значений для f. Есть ли решение, которое не требует, чтобы я вручную создавал таблицу значений?

python-3.x,caching,recursion,

0

Ответов: 1


1 принят

Обратите внимание, что вы можете использовать свою функцию как есть, но вам нужно обеспечить, чтобы каждый свежий вызов не требовал повторения более нескольких сотен уровней до того, как он попал в кешированное значение или рекурсивный базовый случай; например,

f(n)

Я прибегал к этому порой ;-) В более общем плане вы могли бы написать функцию-обертку, которая многократно пытается RecursionError, улавливает nи отступает, называя ее со все меньшими значениями n. Например,

def superf(n, step=400):
    pending = []
    while True:
        pending.append(n)
        try:
            f(n)
            break
        except RecursionError:
            n = max(n - step, 0)
    while pending:
        x = f(pending.pop())
    return x

затем

>>> superf(100000)
5000050001
питон-3.x, кэширование, рекурсия,
Похожие вопросы