Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; b=MHZ6qEIECSjq0kQ/E5l2cRg1W3YyW+BmzynB0ABd4wArV+s8kf3bnAwrRcnXT4Er6u FJhidq4Ach/OHMmI/kximrzVESbO6CwmRJpgIgTjVfyJX9Pgs4188xP8GbjO49koGCAI 1du+w1Z44GDm4IsGpfR9JYBdrthta+iJS5eBs=
MIME-Version: 1.0
In-Reply-To: <0HFvp.18698$vT3.2042@newsfe06.iad>
References: <a78a0ffd-03cc-4540-addb-b8e206d165d5@n2g2000prj.googlegroups.com> <BANLkTimfNQhdE1ZJwP_HN64WwERtUOtBvw@mail.gmail.com> <mailman.1011.1304141265.9059.python-list@python.org> <vcNup.5316$Du7.1273@newsfe04.iad> <ipgl8i$nbm$1@r03.glglgl.eu> <0HFvp.18698$vT3.2042@newsfe06.iad>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 2 May 2011 16:22:35 -0600
Subject: Re: Fibonacci series recursion error
To: harrismh777 <harrismh777@charter.net>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1083.1304375554.9059.python-list@python.org>
Lines: 54
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:4507

On Mon, May 2, 2011 at 3:50 PM, harrismh777 <harrismh777@charter.net> wrote=
:
> Thomas Rachel wrote:
>>>
>>> ... because each recursion level 'return' calls fib() twice, and each o=
f
>>> 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):
>>>> =A0 =A0 if n =3D=3D 1:
>>>> =A0 =A0 =A0 =A0 return(n)
>>>> =A0 =A0 else:
>>>> =A0 =A0 =A0 =A0 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 lo=
ok.
> 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 <=3D 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 <=3D 0:
        return len(inspect.stack())
    else:
        return maxstack(n-1)
print maxstack(15)

This also prints "17".  Note: they're the same.

> =A0the 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.