Understanding recursion with the Fibonacci Series

Question

I am trying to better understand recursion and how return statements work. As such, I'm looking at a piece of code meant to identify the fibonacci number associated with a given term -- in this case, 4. I'm have difficulty understanding the else statement.

def f(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  else:
    return f(n-1) + f(n-2)

f(4)

I have tried using Visualize Python to examine what happens at each step, but I get lost when it hits the else statement.

It looks like it is taking the value of n and subtracting 1, to create a new n value of 3 which it returns to the function definition. So it appears to only be returning the value from the first function in the else statement. However, the else statement is written to return the sum of 2 functions f(n-1) + f(n-2), in which case I thought the return value would be 5? Can you even add 2 functions together?

Thanks in advance for your help.

Here is a link to the code in Visualize Python Sum of 2 functions

Answer 1

When in doubt, just break it down.

The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you hit the base case (the if statements). Now you can carry out all the small computations, and combining the results of those small computations to form a bigger, larger result, until you have your final answer.

Every time a recursive call hits the base case, it will return either 1, or 0, depending on what case was hit. This value will be returned to the previous caller. To understand, consider:

f(1)3 + f(0)3

Note here that the subscript represents the depth of the recursion call tree. The call is made by f(2)2. f(1)3 is computed first, and 1 is returned to f(2)2. f(0)3 is then computed, and 0 is returned to f(2)2. The two return values are summed, and the result is 1.

f(2)2 then returns 1 to whoever called it, which in this case happens to be f(3)1. f(3)1 called f(2)2 + f(1)2, meanwhile this other f(1)2 also returns 1 to f(3)1, who now adds that with the result of f(2)2, to form 2.

f(3)1 now passes 2 to f(4)0, its caller, which happened to call f(3)1 + f(2)1 ... and so it goes.

---

An alternative way of looking at this is to start from the first function call that is actually made: f(4)0.

f(4)0 computes f(3)1 + f(2)1. But to compute f(3)1, it needs to know f(2)2 + f(1)2, and similarly, to compute f(2)1, it needs to know f(1)2 + f(0)2, and so on.

Answer 2

Adding some print statements can also help clarifying the sequence:

def f(n):
    print("Number received:", n)
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        print("---- First recursion ----")
        a = f(n-1)
        print("---- Second recursion ----")
        b = f(n-2)
        print(" a=:",a,"; b=",b,"; returning:", a+b)
        return a + b

print("Final f(4)=", f(4))

Output:

Number received: 4
---- First recursion ----
Number received: 3
---- First recursion ----
Number received: 2
---- First recursion ----
Number received: 1
---- Second recursion ----
Number received: 0
 a=: 1 ; b= 0 ; returning: 1
---- Second recursion ----
Number received: 1
 a=: 1 ; b= 1 ; returning: 2
---- Second recursion ----
Number received: 2
---- First recursion ----
Number received: 1
---- Second recursion ----
Number received: 0
 a=: 1 ; b= 0 ; returning: 1
 a=: 2 ; b= 1 ; returning: 3
Final f(4)= 3