Fibonacci series recursion error

[Chris Angelico]

On Tue, May 3, 2011 at 8:22 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>> 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.
>

Side point: In a massively parallel environment, branching like this
COULD be implemented as a fork. I just don't know of any
implementations of Python that do so. (And of course, it works for
fib() because it needs/uses no global state, which makes the
recursions completely independent. Not all functions are so courteous,
and the compiler can't necessarily know the difference.)

Chris Angelico