Fibonacci series recursion error

[Ian Kelly]

On Mon, May 2, 2011 at 3:50 PM, harrismh777 <harrismh777 at charter.net> wrote:
> Thomas Rachel wrote:
>>>
>>> ... because each recursion level 'return' calls fib() twice, and each of
>>> those calls fib() twice, and you get the point...
>>
>> yes - but they are called one after the other, so the "twice" call
>> counts only for execution speed, not for recursion depth.
>
>>>> def fib(n):
>>>>     if n == 1:
>>>>         return(n)
>>>>     else:
>>>>         return (fib(n-1)+fib(n-2))
>
> They *are not* called one after the other in the sense that there is ever
> only one level of recursion with each call (not at all). Take a closer look.
> Each call to fib() forces a double head, and each of those forces another
> double head (now four), and so on...

The branching factor has nothing to do with the maximum stack depth.
If you don't believe me, consider this little script:

import inspect
def maxstack(n):
    if n <= 0:
        return len(inspect.stack())
    else:
        return max(maxstack(n-1), maxstack(n-2))
print maxstack(15)

This prints "17".

Now consider this script, which is similar but singly-recursive:

import inspect
def maxstack(n):
    if n <= 0:
        return len(inspect.stack())
    else:
        return maxstack(n-1)
print maxstack(15)

This also prints "17".  Note: they're the same.

>  the recursion depth exception of the
> OP testifies against your theory.

The OP's recursion depth exception was because a malformed base case
made the recursion infinite.  It had nothing to do with the branching
factor.