+ 1

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

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?

23rd Jun 2017, 6:04 AM
Ava Nicole
Ava Nicole - avatar
42 Respuestas
0
Okay I think it's starting to make sense
23rd Jun 2017, 7:30 PM
Ava Nicole
Ava Nicole - avatar
+ 1
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 :)
23rd Jun 2017, 7:54 AM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
That's it ! In this example at least. Each time a function calls itself.
23rd Jun 2017, 4:52 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
(Rather 0 to n, as it will work with n==0) Yes, that's it
23rd Jun 2017, 6:37 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
Because it is the index that you sum up and index values go from 0 to n. No problem, I was glad to help :)
23rd Jun 2017, 6:55 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
So when does recursiveSolution_Helper return back to recursiveSolution?
23rd Jun 2017, 6:58 PM
Ava Nicole
Ava Nicole - avatar
+ 1
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?
23rd Jun 2017, 7:08 PM
Ava Nicole
Ava Nicole - avatar
+ 1
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
23rd Jun 2017, 7:09 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
yes, that is why there is the result of 5 additions while there is only 4 recursive calls of recursionSolution_Helper
23rd Jun 2017, 8:10 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
That's it !
23rd Jun 2017, 8:13 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 1
And each recursive call solves a small part of the bigger issue
23rd Jun 2017, 8:13 PM
Ava Nicole
Ava Nicole - avatar
+ 1
Lol that phrase
23rd Jun 2017, 8:17 PM
Ava Nicole
Ava Nicole - avatar
0
So everytime you go to the else statement you make a recursive call right?
23rd Jun 2017, 3:28 PM
Ava Nicole
Ava Nicole - avatar
0
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?
23rd Jun 2017, 5:13 PM
Ava Nicole
Ava Nicole - avatar
0
Exactly ! But it do the same with every call of functions in functions, not only recursive ones
23rd Jun 2017, 5:56 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
0
So you're saying if there was another function call of some sort in here it would also be included?
23rd Jun 2017, 6:09 PM
Ava Nicole
Ava Nicole - avatar
0
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)))
23rd Jun 2017, 6:12 PM
Ava Nicole
Ava Nicole - avatar
0
Could you help explain this one?
23rd Jun 2017, 6:12 PM
Ava Nicole
Ava Nicole - avatar
0
Sorry some of the stuff might get moved around
23rd Jun 2017, 6:13 PM
Ava Nicole
Ava Nicole - avatar
0
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
23rd Jun 2017, 6:31 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar