Fibonacci Sequence and Long numbers.

[John W. Baxter]

In article <slrn8tq481.21q.hzhu at rocket.knowledgetrack.com>, 
hzhu at users.sourceforge.net wrote:

> 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

Neil, the solution would be to rewrite fib() as a non-recursive function 
(which is not that hard in the case of fib()), and avoid the recursion 
limit.  [The limit is there to avoid annoyances like
def oops(x)
    oops(x)

oops(x)

(which are usually disguised a bit better than that, and unintentional).  
And to avoid even "correct" functions such as your fib which exhaust 
memory in the real world (faster in the Macintosh real world than in 
some others ;-)).]

Fibonacci is done recursively by habit, because it's such good theatre.  
;-)

  --John

-- 
John W. Baxter   Port Ludlow, WA USA  jwbnews at scandaroon.com