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