Fibonacci series recursion error

Ian Kelly ian.g.kelly at gmail.com
Sat Apr 30 07:27:14 CEST 2011


On Fri, Apr 29, 2011 at 9:57 PM, Jason Friedman <jason at powerpull.net> wrote:
> The first call to fib() recursively calls fib() twice.  Each of those
> will call fib() twice.  Each of those will call fib() twice.  Pretty
> soon, you've got a lot of calls.

Which is hell for the running time, but doesn't answer the question of
why the maximum recursion depth is exceeded, since the fact is that if
the function were properly coded, the call stack for fib(20) would
never be more than 20 entries deep at any one time.

The actual problem, as Gary pointed out, is that the base case is incomplete.



More information about the Python-list mailing list