Hi I need help with the following code:
if top == 0:
return top * walk(top - 1)
Now when I read this code I thought the answer would be 2 but it come to 0 .can someone please explain how.
top * walk(top - 1)
2 * walk(2 - 1)
2 * walk(1)
so I think the return value should be 2 but it is 0 .How?
You have a recursion issue where it will always return 0 for any non-negative value and will never return for a negative value.
Here is what happens for positive values (I’ll use the case of 2 that you used):
- top = 2 which is not 0 yet so we go to the recursive else condition resulting in 2 * walk(2 - 1) or 2 * walk(1)
- inside the first recursion top = 1 which is still not 0 so we go to the recursive else condition resulting in 2 * (1 * walk(1 - 1)) or 2 * (1 * walk(0))
- inside this second recursion top = 0 so the condition is true and we return 0 from this layer of the recursion meaning our result now looks like 2 * (1 * 0) which results in 0
For any non negative value the recursion ends when you finally return 0 and that will get multiplied by everything before resulting in 0.
A negative number is even worse since it would never get to the base condition so you have an infinite recursion that will either keep trying forever or throw an error (cannot remember which Python does).
Basically you probably have the wrong base case for your recursion. You probably want a base case that returns 1 (looks like you are basically implementing the factorial function).
Thank you so much for your reply.
One thing I don’t understand is that there is no loop so why the function is not executed only once ?.Why we have a recursive issue here.
I really thought it is simple ,execute function only once.and print the result.As 'if ’ block doesn’t satisfy the condition ,the control goes to ‘else’ block and then print the result.
A function which calls itself is recursive which means it must resolve the recursive call in order to return from the outer call. You can check out Wikipedia on the subject: Recursion - Wikipedia
If your function called a different function, you have no issue, but you can even have recursion between various functions if they form a loop (like funcA calls funcB calls funcC calls funcA).
In our simple case the initial call to walk(2) cannot be resolved without determining the result of walk(1) which cannot be resolved without determining the result of walk(0). The innermost one gets resolved and then each of the recursive calls gets resolved until the whole thing can return. Try adding a couple of print statement so you can see when the recursive calls happen:
print("walk called with " + top)
if top == 0:
result = top * walk(top - 1)
print("recursive call returned from walk("+top-1+")")
print("final result = " + walk(2))
It should print:
walk called with 2
walk called with 1
walk called with 0
recursive call returned from walk(0)
recursive call returned from walk(1)
final result = 0