0

Let me stop you right there, I already know you can adjust the maximum allowed depth.

But I would think this function, designed to calculate the nth Fibonacci number, would not exceed it, owing to the attempted memoization.

What am I missing here?

def fib(x, cache={1:0,2:1}):
    if x is not 1 and x is not 2 and x not in cache: cache[x] = fib(x-1) + fib(x-2)
    return cache[x]
4

5 回答 5

2

您的代码有效，只需设置递归限制（默认为 1000）：

>>> def fib(x, cache={1:0,2:1}):
...     if x is not 1 and x is not 2 and x not in cache: cache[x] = fib(x-1) + f
ib(x-2)
...     return cache[x]
...
>>> from sys import setrecursionlimit
>>> setrecursionlimit(4001)
>>> fib(4000)
24665411055943750739295700920408683043621329657331084855778701271654158540392715
48090034103786310930146677221724629877922534738171673991711165681180811514457211
13771400656054018493704811431159158792987298892998378107544456316501964164304630
21568595514449785504918067352892206292173283858530346012173429628868997174476215
95754737778371797011268738657294932351901755682732067943003555687894170965511472
22394287423465133129791428666544293424932758353804445807459873383767095726534051
03186366562265469193320676382408395686924657068094675464095820220760924728356005
27753139995364477320639625889904027436038223654786222515006804845418392308019640
53848249082837958012652040193422565794818023898141209364892225521425081077545093
40549694342959926058170589410813569880167004050051440392247460055993434072332526
101572422443738016276258104875526626L
>>>

原因是，如果你想象一棵大树，你的根节点是 4000，它连接到 3999 和 3998。你一直沿着树的一个分支向下走，直到遇到基本情况。然后你回来从底部构建缓存。所以树的深度超过 1000，这就是你达到极限的原因。

于 2013-11-06T00:50:54.943 回答
2

这里的问题是 tdelaney 在评论中指出的问题。

您正在向后填充缓存，从x下到2.

这足以确保您只执行线性数量的递归调用。第一次调用fib(4000)只进行 3998 次递归调用。

但是3998 > sys.getcursionlimit()，所以这无济于事。

于 2013-11-06T00:48:43.760 回答
1

要添加到讨论问题评论中，想总结一下：

  • 您在递归步骤之后添加到缓存中 - 因此您的缓存没有做太多。
  • 您还在所有调用中引用相同的缓存值。不确定这是否是您想要的，但这就是行为。
  • 这种递归风格不是 Python 惯用的。但是，惯用的 Python是使用诸如 memoization 装饰器之类的东西。例如，请看这里：https ://wiki.python.org/moin/PythonDecoratorLibrary#Memoize （与您的确切示例）
于 2013-11-06T00:20:43.063 回答
0

使 memoization 能够很好地解决此类问题的诀窍是从您还不知道的第一个值开始，然后朝着您需要返回的值努力。这意味着避免自上而下的递归。迭代计算斐波那契值很容易。这是一个带有备忘录列表的非常紧凑的版本：

def fib(n, memo=[0,1]):
    while len(memo) < n+1:
        memo.append(memo[-2]+memo[-1])
    return memo[n]

这是一个快速演示运行（运行速度非常快）：

>>> for i in range(90, 101):
    print(fib(i))

2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738
19740274219868223167
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
354224848179261915075

>>> fib(4000)
39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875
于 2013-11-06T00:54:42.250 回答
0

也许这有助于可视化，出了什么问题：

def fib(x, cache={0:..., 1:0, 2:1}):
    if x not in cache: cache[x] = fib(x-1) + fib(x-2)
    return cache[x]

for n in range(4000): fib(n)
print(fib(4000))

当您明确地自下而上构建缓存时，可以完美地工作。（在运行时不评估默认参数是一件好事。）

顺便说一句：您最初的字典是错误的。fib (1) 是 1 而不是 0。不过，我在方法中保留了这个编号偏移量。

于 2013-11-06T00:47:30.817 回答