On Tue, May 3, 2011 at 8:22 AM, Ian Kelly <ian.g.ke...@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 -- http://mail.python.org/mailman/listinfo/python-list