CODEWITHSUNDEEP
python
prosseek
prosseek

Reputation: 190769

Issue when computing fibonacci number with recursion in python

I have this code for computing fibonacci numbers using cache (dictionary).

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)

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

This is the result with 2000 as an input.

....
caching 1008
1007
caching 1007
1006
caching 1006
1005
caching 1005

This is a result with 1000 as an input. 

....
8
caching 8
7
caching 7
6
caching 6
5
caching 5

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?

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.

Upvotes: 2

Views: 537

Answers (4)

DhruvPathak
DhruvPathak

Reputation: 43235

Python has a default recursion limit set to 1000. You need to increase it in your program.

import sys

sys.setrecursionlimit(5000)

From : http://docs.python.org/2/library/sys.html#sys.setrecursionlimit

sys.setrecursionlimit(limit)

Set the maximum depth of the Python interpreter stack to limit. 
This limit prevents infinite recursion from causing an overflow of the C 
stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the
limit higher when she  has a program that requires deep recursion and a 
platform that supports a higher limit. This should bedone with care, because
a too-high limit can lead to a crash.

Upvotes: 2

mgilson
mgilson

Reputation: 309899

You don't really gain anything by storing the cache as a dictionary since in order to calculate f(n) you need to know f(n-1) (and f(n-2)). In other words, your dictionary will always have keys from 2-n. You might as well just use a list instead (it's only an extra 2 elements). Here's a version which caches properly and doesn't hit the recursion limit (ever):

import time
cache = [1,1]

def dynamic_fib(n):
    #print n
    if n >= len(cache):
        for i in range(len(cache),n):
            dynamic_fib(i)

        cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))
        print "caching %d" % n

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    a = dynamic_fib(4000)
    print "Dynamic",a
    print (time.time() - start)

Note that you could do the same thing with a dict, but I'm almost positive that a list will be faster.

Just for fun, here's a bunch of options (and timings!):

def fib_iter(n):
    a, b = 1, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

memo_iter = [1,1]
def fib_iter_memo(n):
    if n == 0:
        return 1
    else:
        try:
            return memo_iter[n+1]
        except IndexError:
            a,b = memo_iter[-2:]
            for i in xrange(len(memo_iter),n+2):
                a, b = b, a + b
                memo_iter.append(a)
            return memo_iter[-1]

dyn_cache = [1,1]
def dynamic_fib(n):
    if n >= len(dyn_cache):
        for i in xrange(len(dyn_cache),n):
            dynamic_fib(i)

        dyn_cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))

    return dyn_cache[n]

dyn_cache2 = [1,1]
def dynamic_fib2(n):
    if n >= len(dyn_cache2):
        for i in xrange(len(dyn_cache2),n):
            dynamic_fib2(i)

        dyn_cache2.append(dyn_cache2[-1] + dyn_cache2[-2])

    return dyn_cache2[n]

cache_fibo = [1,1]
def dyn_fib_simple(n):
   while len(cache_fibo) <= n:
        cache_fibo.append(cache_fibo[-1]+cache_fibo[-2])
   return cache_fibo[n]

import timeit
for func in ('dyn_fib_simple','dynamic_fib2','dynamic_fib','fib_iter_memo','fib_iter'):
    print timeit.timeit('%s(100)'%func,setup='from __main__ import %s'%func),func


print fib_iter(100)
print fib_iter_memo(100)
print fib_iter_memo(100)
print dynamic_fib(100)
print dynamic_fib2(100)
print dyn_fib_simple(100)

And the results:

0.269892930984 dyn_fib_simple
0.256865024567 dynamic_fib2
0.241492033005 dynamic_fib
0.222282171249 fib_iter_memo
7.23831701279 fib_iter
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101

Upvotes: 2

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 250931

A recursion free version:

def fibo(n):
   cache=[1,1]
   while len(cache) < n:
       cache.append(cache[-1]+cache[-2])
   return cache

Upvotes: 1

ConfusedProgrammer
ConfusedProgrammer

Reputation: 616

It's probably because of the limit of stack depth, which results in an RuntimeError. You can increase the stack's recursion limit by calling

sys.setrecursionlimit(<number>)

of the sys module.

Upvotes: 0

Related Questions