15

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

cs95
  • 379,657
  • 97
  • 704
  • 746
efw
  • 449
  • 3
  • 16
  • 4
    It's not adding two functions, it's adding the integers returned by two calls to a function. Each call is entirely independent, in particular each one has its own private value for `n`. – jasonharper Sep 21 '17 at 00:12

2 Answers2

40

When in doubt, just break it down.

enter image description here

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.

cs95
  • 379,657
  • 97
  • 704
  • 746
  • This is brilliant. Thank you. I am still confused about the '+' sign in the else statement, which is an operator, but clearly does not function as such in the else statement. Can someone offer an explanation for that? On another note, the visualizer I was using did not show the two functions operating in tandem. It was only showing results from the first function. Don't know why that was the case, but that's what confused me. – efw Sep 21 '17 at 04:31
  • 1
    @efw I understand where you're coming from. Like I mentioned, the recursion tree is a little counter-intuitive to that actual call stack. It's more like f(4)0 -> f(3)1 -> f(2)2 -> f(1)3 -> 1 -> f(0)3 -> 0 -> f(1)2 -> ... and so on. Left to right evaluation in python. When examining the recursion tree, we traverse level wise. This is not how it is actually done during execution. – cs95 Sep 21 '17 at 05:35
  • I think I understand it now. The code is first building a "list" of n values, at the else statement, through the process of recursion. Eventually, the n values satisfy one of the two conditionals at which point integer values are returned, the total of which are summed in the final step. Thanks again for your help. – efw Sep 21 '17 at 15:46
4

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
rnso
  • 23,686
  • 25
  • 112
  • 234
  • This code cannot handle huge numbers in the input. You should consider the runtimes too. – Akshay Sapra Dec 21 '18 at 05:52
  • 2
    @Akshay Sapra I agree that avoiding memoization makes the function inflexible, but OP asked 'how the return statements work'. Grasping the fundamentals of recursion is decently addressed here, which is the question at hand. – Daniel Scott Feb 27 '19 at 04:34