Fibonacci series recursion error

[Chris Angelico]

On Tue, May 3, 2011 at 7:50 AM, harrismh777 <harrismh777 at charter.net> 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 recursion depth exception of the
> OP testifies against your theory.

def fib(n):
	if n==1:
		return n
	return fib(n-1)+fib(n-2)


dis.dis(fib)
  2           0 LOAD_FAST                0 (n)
              3 LOAD_CONST               1 (1)
              6 COMPARE_OP               2 (==)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP

  3          13 LOAD_FAST                0 (n)
             16 RETURN_VALUE
        >>   17 POP_TOP

  4          18 LOAD_GLOBAL              0 (fib)
             21 LOAD_FAST                0 (n)
             24 LOAD_CONST               1 (1)
             27 BINARY_SUBTRACT
             28 CALL_FUNCTION            1
             31 LOAD_GLOBAL              0 (fib)
             34 LOAD_FAST                0 (n)
             37 LOAD_CONST               2 (2)
             40 BINARY_SUBTRACT
             41 CALL_FUNCTION            1
             44 BINARY_ADD
             45 RETURN_VALUE

The recursion is in the last block. Note that it calls a function,
then keeps going. It doesn't fork. There are two CALL_FUNCTION
opcodes, called *sequentially*. In terms of the call stack, there is
only ever one of those two calls active at any given time. Also, as
earlier pointed out, the reason for the stack overflow is that fib(2)
will call fib(1) and fib(0), and fib(0) will call fib(-1) and fib(-2),
etc. Changing the operator from == to <= in the conditional return
will solve this.

Chris Angelico