Why am I exceeding max recursion depth?

Question

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]

Answer 1

The problem here is the one that tdelaney pointed out in a comment.

You are filling the cache in backward, from x down to 2.

That is sufficient to ensure that you only perform a linear number of recursive calls. The first call to fib(4000) only makes 3998 recursive calls.

But 3998 > sys.getcursionlimit(), so that doesn't help.

Answer 2

Your code works, just set the recursion limit (default is 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
>>>

The reason is, if you imagine a large tree, your root node is 4000, which connects to 3999 and 3998. you go all the way down one branch of the tree until you hit a base case. Then you come back up building the cache from the bottom. So the tree is over 1000 deep which is why you hit the limit.

Answer 3

To add to the discussion question comments, wanted to summarize:

• You're adding to the cache after the recursive step -- thus your cache isn't doing much.
• You're also referring to the same cache value in all the calls. Not sure if that's what you want, but that's the behavior.
• This style of recursion isn't idiomatic Python. However, what is idiomatic Python is to use something like a memoization decorator. For an example, look here: https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize (With your exact example)

Answer 4

Maybe this helps to visualise, what is going wrong:

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))

Works perfectly as you explicitely build the cache bottom up. (It is a good thing that default arguments are not evaluated at runtime.)

Btw: your initial dictionary is wrong. fib (1) is 1 and not 0. I kept this numbering offset in my approach, though.

Answer 5

The trick to making memoization work well for a problem like this is to start at the first value you don't yet know and work up towards the value you need to return. This means avoiding top-down recursion. It's easy to iteratively compute Fibonacci values. Here's a really compact version with a memo list:

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

Here's a quick demo run (which goes very fast):

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

2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738
19740274219868223167
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
354224848179261915075

>>> fib(4000)
39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875