Issue when computing fibonacci number with recursion in python
<p>I have this code for computing fibonacci numbers using cache (dictionary).</p>

<pre><code>cache = {} 
def dynamic_fib(n):
    print n
    if n == 0 or n == 1:
        return 1
    if not (n in cache):
        print "caching %d" % n
        cache[n] = dynamic_fib(n-1) + dynamic_fib(n-2)

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    print "DYNAMIC: ", dynamic_fib(2000)
    print (time.time() - start)
</code></pre>

<p>I works fine with small numbers, but with more than 1000 as an input, it seems to stop.</p>

<p>This is the result with 2000 as an input.</p>

<pre><code>....
caching 1008
1007
caching 1007
1006
caching 1006
1005
caching 1005
</code></pre>

<p>This is a result with 1000 as an input. </p>

<pre><code>....
8
caching 8
7
caching 7
6
caching 6
5
caching 5
</code></pre>

<p>It looks like that after 995 storage into the dictionary, it just hangs.
What might be wrong in this? What debugging technique can I use to see what went wrong in python?</p>

<p>I run python on Mac OS X 10.7.5, I have 4G bytes of RAM, so I think some KB (or even MB) of memory usage doesn't matter much. </p>
