Recursion on Fibonacci Sequence

fibonacci, python, recursion

Solution

Here is the full expansion of what happens:

fib(5) expands to fib(4)+fib(3)
  fib(4) expands to fib(3)+fib(2)
    fib(3) expands to fib(2)+fib(1)
      fib(2) expands to fib(1)+fib(0)
        fib(1) evaluates to 1
        fib(0) evaluates to 1
      fib(1) evaluates to 1
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
  fib(3) expands to fib(2)+fib(1)
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
    fib(1) evaluates to 1

If you count the ones, you get 8 as the answer.

Problem

I need some help in understanding the processing that happens here, so let´s say I call `fib(5)` I want the fibonacci 5, which is 8. But my brain in trying to understand the algorithm says it´s not. This is how i (wrongly) think: ``` return fib(4) + fib(3) // Stack frame 1 return fib(3) + fib(1) // Stack frame 2 ``` now cause x is 1 `fib(1)`, the conditional statement `if x == 0 or x == 1:` causes the recursion to end. Which according to my logic would become 3+1+4+3. Please correct my faulty logic. ``` def fib(x): """assumes x an int >= 0 returns Fibonacci of x""" assert type(x) == int and x >= 0 if x == 0 or x == 1: return 1 else: return fib(x-1) + fib(x-2) ```

Original source