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

Abdulrahim Jamil no way the answer could be 203, but I accept 303
If you want the answer to be 303, You have to construct the else statement like this
else:
n -= 1
return n + f(n) + 100
The reason for this, is that the use of f(n-1) does not add n to the next recursive call, so the variable get discarded and the function call itself again to the stack
to modify this function to return 203, you should modify the recursion base to return -97 instead of 0
if n == 0:
return -97
else:
n -= 1
return n + f(n) + 100

Answer 6

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