Home Original page

Fibonacci Sequence and Long numbers.

Huaiyu Zhu hzhu at users.sourceforge.net
Thu Oct 5 19:32:47 EDT 2000 
On Thu, 05 Oct 2000 15:35:43 -0700, Neil Macneale <macneale at cats.ucsc.edu>
wrote: 
>
>>>> cache = []
>>>> cache.insert(0, 0L)
>>>> cache.insert(1, 1L)
>>>> def fib(i):
>...    if len(cache) > i:
>...       return cache[i]
>...    cache.insert(i, fib(i-1) + fib(i-2))
>...    return cache[i]
>... 
>
>All seems good and well to this point.  But when I try:
>
>>>> fib(1000)
>
>I get a whole bunch of recursive erros which tell me there is an Integer 
>addition error.

Are you seeing RuntimeError: Maximum recursion depth exceeded?

If so, this is because fib is calling fib recursively.  When you call fib(n)
there are n-len(cache) open function calls before they are fulfilled one by
one.  On my Linux, fib(len(cache)+997) works, but fib(len(cache)+998) fails.

Huaiyu
More information about the Python-list mailing list