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]

Standard reminder: don't use `is` and `is not` where you mean `==` and `!=`. `is` tests identity, not equality. — DSM, Nov 06 '13 at 00:14
x = 4000 is my test. And yes @DSM, I know...I just write it sometimes when I'm testing short snippets of code involving small ints, since identity/equality is the same in that case. — temporary_user_name, Nov 06 '13 at 00:15
I don't think it's causing your current issue, but [beware of using mutables as default arguments](http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument) — kojiro, Nov 06 '13 at 00:17
To add to what @DSM said, you should also probably not explicitly check for `cache`'s keys in the if, just check cache membership. A hash lookup is fast enough to not have to repeat yourself. As to why your cache is not doing much right now, is because `fib` works backwards to 0. Your algorithm is always ahead of your cache, if that makes sense. — yan, Nov 06 '13 at 00:17
Yes, I know @kojiro. I'm taking advantage of that here deliberately in an attempt to memoize, but I'm doing it wrong. I'm already partially onto why it's not working; I'm just trying to figure out how to do it correctly. — temporary_user_name, Nov 06 '13 at 00:17
you are filling up the memo backwards (adding 4000, then 3999, etc...) so none of the smaller numbers are in there yet. — tdelaney, Nov 06 '13 at 00:18
Recursion is not idiomatic in Python. You must convert the recursive algorithm to its iterative form. which is trivial. Python lacks tail call optimizations common in functional languages and the recursion stack is limited to 999 (you can change this default, but it is limited, hence I'm daring to consider the recursive form incorrect in Python). — Paulo Scardine, Nov 06 '13 at 00:18
@Aerovista: `identity/equality is the same in that case` that is simply not true. The fact that CPython caches some small int is implementation detail, other Python implementation, code optimizers, and future CPython might freely cause that assumption to be untrue. — Lie Ryan, Nov 06 '13 at 00:21
And even if you do want to rely on that implementation detail of CPython, the fact it's not true for any default build or any major version of CPython for numbers on the order of 4000 means you're explicitly guaranteeing that your cache _won't_ work. — abarnert, Nov 06 '13 at 00:41
@PauloScardine Nevertheless, there are workarounds that allow for TCO, when you really want it, like e.g. this one. http://code.activestate.com/recipes/474088/ — Hyperboreus, Nov 06 '13 at 00:42
@Hyperboreus: clever hack, thanks for the link. If you profile both solutions, it becomes clear that iteration is way more idiomatic in Python compared to recursion (function call is expensive in Python). — Paulo Scardine, Nov 06 '13 at 00:52
@PauloScardine It is not only more idiomatic, but also the only viable option and that is a pity. (Basically the lack of (optional) TCO in python is about the only thing that bothers me with python, which in general terms is my favorite language these days.) (Edit: And people who get religious about PEP-8) — Hyperboreus, Nov 06 '13 at 01:04

score 2 · Accepted Answer · answered Nov 06 '13 at 00:48

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.

score 2 · Answer 2 · answered Nov 06 '13 at 00:50

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.

score 1 · Answer 3 · answered Nov 06 '13 at 00:20

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)

@Aerovistae: Look at http://stackoverflow.com/questions/15047116/a-iterative-algorithm-for-fibonacci-numbers for iterative solutions. — Paulo Scardine, Nov 06 '13 at 00:26

score 0 · Answer 4 · answered Nov 06 '13 at 00:47

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.

score 0 · Answer 5 · answered Nov 06 '13 at 00:54

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

Why am I exceeding max recursion depth?

5 Answers5