+ 1

# Recursion In Python

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))

1st Jun 2023, 5:01 PM
DevAbdul + 4
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
1st Jun 2023, 5:41 PM
Per Bratthammar + 3
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
1st Jun 2023, 5:18 PM
Per Bratthammar + 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.
1st Jun 2023, 6:26 PM
DevAbdul + 1
Per Bratthammar it doesn't start with zero, it starts with a 3
1st Jun 2023, 5:21 PM
DevAbdul + 1
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
1st Jun 2023, 5:43 PM
Mirielle 0
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
1st Jun 2023, 6:28 PM
DevAbdul 