On Mon, May 2, 2011 at 3:50 PM, harrismh777 <harrismh...@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. -- http://mail.python.org/mailman/listinfo/python-list