Recursion In Python

Question

Can someone please explain why the following code prints 300 instead of 203

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

print(f(3))

Answer 1

Hi, again, Abdulrahim Jamil !

But it’s recursion. Every value f(n) is built on previouse values f(n-1), in that way it’s showed below. So f(0) -> f(1), f(1) -> f(2), …, f(n-1) -> f(n):

f(0) = 0
f(1) = f(0) + 100 = 100
f(2) = ff1) + 100 = 100 + 100 = 200
f(3) = f(2) + 100 = 200 + 100 = 300

Answer 2

Hi, Abdulrahim Jamil !

Why should it be 203!

It’s start with 0, and add 100 every time you ingrease n with 1

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

Answer 3

Per Bratthammar thanks for clarifying that, now I remember that the function stack also works like a normal stack i.e it uses the LIFO technique, I now understand how it works. I had initially thought it would work like this:

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

I now see why it couldn't have worked that way and I think it's because it return statement wasn't written like this:

return n + f(n - 1) + 100

As you would have done when calculating the sum of numbers below a number n (without the 100 of course!).

Thanks again Per Bratthammar.

Answer 4

Per Bratthammar it doesn't start with zero, it starts with a 3

Answer 5

Mirielle I totally agree with you, as I mentioned in my reply to Per Bratthammar I approached it the same way I would a function calculating the sum of all numbers below a certain number n. Thanks