Does anyone have any suggestions on how to understand how recursive functions are executed in python?

Question

I'm having issues understanding how code is executed in recursive functions, so I was wondering if anyone has any suggestions on understanding how it's executed?

Answer 1

Okay I think it's starting to make sense

Answer 2

I will explain it with an example :
def fact(n):
if n<0:
return -1
elif n==0 or n==1:
return 1
else:
return n*fact(n-1)
fact(4)

During the call with n==4, it will go to the else statement. There, it will need the result of fact(3) to be able to return something.
It will be the same for n==3 and fact(2), and n==2 and fact(1).
When fact will be call with n==1, it will go to the elif statement and return 1.
There, it will go back to n==2 and return 2*1.
Next, to n==3 and return 3*(2*1).
Lastly, to n==4 and return 4*(3*2*1).

The else statement is the recursive call while the elif statement is the way not to go recursively infinitely.
The if statement is just an error checking to prevent the user from using negative numbers.

Hope I was clear enough :)

Answer 3

That's it ! In this example at least. Each time a function calls itself.

Answer 4

(Rather 0 to n, as it will work with n==0)
Yes, that's it

Answer 5

Because it is the index that you sum up and index values go from 0 to n.
No problem, I was glad to help :)

Answer 6

So when does recursiveSolution_Helper return back to recursiveSolution?

Answer 7

So when it hits the call of itself it goes back to the top and then the if statement and returns the sum. Returnvalue in the caller function then is replaced with the sum which is returned? So what's the point of the bottom return ReturnValue statement?

Answer 8

Without it, your function would return nothing if index!=n on its first call.
You could do return recursiveSolution_Helper(n,sum,index) not to use another variable but that is another story

Answer 9

yes, that is why there is the result of 5 additions while there is only 4 recursive calls of recursionSolution_Helper

Answer 10

That's it !

Answer 11

And each recursive call solves a small part of the bigger issue

Answer 12

Lol that phrase

Answer 13

So everytime you go to the else statement you make a recursive call right?

Answer 14

This is also related to the call stack right? Like each recursive call adds to the call stack and every time one finishes it goes back to the call before it?

Answer 15

Exactly ! But it do the same with every call of functions in functions, not only recursive ones

Answer 16

So you're saying if there was another function call of some sort in here it would also be included?

Answer 17

def recursiveSolution(n):
sum = 0
index = 0
returnValue = recursiveSolution_Helper(n,sum,index)
return returnValue

def recursiveSolution_Helper(n,sum,index):
if index == n:
sum = sum + index
return sum
else:
sum = sum + index
index = index + 1
returnValue = recursiveSolution_Helper(n,sum,index)
return returnValue

print("Recursive solution " + str(recursiveSolution(5)))

Answer 18

Could you help explain this one?

Answer 19

Sorry some of the stuff might get moved around

Answer 20

Your example is the same, there is the stop part (which end the recursive calls), the if statement, and the recursive part, the else statement