Fibonacci Sequence and Long numbers.

[tye4]

Python has a fixed level of recursion; 9999 to be exact.
That is, x() can call x() 9999 times before Python
spits out an error msg.

This li'l script prints out the max depth of recursive calls

class foo:
    pass

def recurse(f, depth):
    f.depth = depth
    recurse(f, depth+1)

>>> f = foo()
>>> recurse(f, 1)
Runtime error: max recursion depth exceeded

>>> f.depth
9999


Try using a non-recursive fibonacci fn.

def fib_nr(n):
    cache = []
    a = 0L
    b = 0L
    while b < n:
       cache.append(b)
       temp = a + b
       a = b
       b = temp
    #end loop
    return cache

>>> fib_nr(10)
[1, 1, 2, 3, 5, 8]

or

>>> fib_nr(1000000L)


-tye4


Neil Macneale wrote:

> Hi all,
>
> I am using MacPython 1.5.2 on a G3 powerbook,  and I am getting a
> strange result from a fibonachi function. This is what I typed at the
> command line:
>
> >>> 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]
> ...
> >>> fib(1)
> 1L
> >>> fib(2)
> 1L
> >>> fib(3)
> 2L
> >>> for i in range(10):
> ...    print fib(i)
> ...
> 0L
> 1L
> 1L
> 2L
> 3L
> 5L
> 8L
> 13L
> 21L
> 34L
> >>> fib(100)
> 354224848179261915075L
>
> 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.  The strangest part is that if I slowely increment, by a
> few hundred, up to 1000,  it works fine.
>
> >>> fib(180)
> 18547707689471986212190138521399707760L
> >>> fib(200)
> 280571172992510140037611932413038677189525L
> >>> fib(220)
> 4244200115309993198876969489421897548446236915L
> >>> fib(400)
> 1760236806450139664682269453924112507703843833044921918867259928965753450
> 44216019675L
> >>> fib(600)
> 1104330705729522423464322467677182859425902373575556063800088918752777017
> 05731473925618404421867819924194229142447517901959200L
> >>> fib(1000)
> 4346655768693745643568852767504062580256466051737178040248172908953655541
> 7949051890403879840079255169295922593080322634775209689623239873322471161
> 642996440906533187938298969649928516003704476137795166849228875L
>
> I went up all the way to 5000 this way,  but when I tried fib(7000) I
> got all the same errors again.
>
> What is going on?
>
> Thanks for any insight,  Neil Macneale