On 01/-10/-28163 02:59 PM, jc wrote:
# Get Fibonacci Value
# Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)
#
# n = 900 is OK
# n = 1000 is ERROR , Why
#
# What Wrong?
#
cache = []
def fibo( n ):
try:
if cache[n] != -1:
return cache[n]
else:
if 0 == n:
r = 0
elif 1 == n:
r = 1
else:
r = fibo(n-1) + fibo(n-2)
cache[n] = r
return r
except:
print "EXCEPT: " + str(n)
if __name__ == '__main__':
# This n = 900 is OK
# But n = 1000 is ERROR
n = 900
cache = range(0 , n + 1 , 1)
for i in cache:
cache[i] = -1
print "Fibo(" + str(n) + ") = " + str(fibo(n))
print "\n"
print "\n"
It'd be really nice if you bothered to state what "ERROR" you get. Show
the traceback or since the output is pretty long, at least show part of
it. copy/paste it from the shell.
In any case, it's clearly a recursion problem, due to the default limit
of the CPython stack (1000). This succeeds for 999, and gets a stack
overflow at 1000.
A solution that lets you go much higher would be to insert before the lines:
if cache[n] != -1:
return cache[n]
The following:
if n > MAXDEPTH:
if n%MAXDEPTH:
for i in xrange(0, n, 200):
fibo(i) #calc value just to prefill the cache
where an easy value for MAXDEPTH is 200.
Think about what this does, and you should see why it'll help.
I tried it for 100,000 and it doesn't blow up. I didn't however check
any of the other logic.
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
