CODEWITHSUNDEEP
python
rob hayes
rob hayes

Reputation: 9

Understanding the return value of the Fibonacci Sequence in Python 3

Please explain how the output value of:

def f(x):
   if x == 0:
      return 0
   return x + f(x -1)

f(3)

is 6.

Upvotes: 0

Views: 47

Answers (1)

Giorgi Tsiklauri
Giorgi Tsiklauri

Reputation: 11120

Let's depict how do your recursive calls look like:

f(3) = 3 + f(2)
           f(2) = 2 + f(1)
                      f(1) = 1 + f(0)
                                 f(0) = 0

Now, let's poll the call stack from the top to down, starting with the base case (last) call:

  • f(0) = 0
  • f(1) = 1 + f(0) = 1 + 0 = 1
  • f(2) = 2 + f(1) = 2 + 1 = 3
  • f(3) = 3 + f(2) = 3 + 3 = 6.

So, the final value returned by f(3) is 6.

Note, that each f(n) call is pushed on top of the stack, until recursion hits the base case n==0, from which, calls are unwound from top to down.

Upvotes: 3

Related Questions