where the function has problem? n = 900 is OK , but n = 1000 is ERROR

[Dave Angel]

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