I personally, have had a hard time understanding it and it happened I had those light bulb moments while having a bath and thinking of a challenge I had just solved using recursion. Yeah, some times you solve challenges and it snaps - it works but deep down, you know you haven't fully understood why it worked. Don't worry, if it happens to you, the bad news is that you are now alone. Though I would probably say "Its because we haven't been able to intuitively understand the problem/solution".
Back to bathing and thinking of why my solution worked - well it just had to, I had even dreamt about solving the challenge. The good news is I figured out the whole stuff and yes, I figured it out the intuitive way (I had that priceless "Ahaa" moment when you suddenly shout "UP NEPA" - just incase you dont understand the Ahaa moment, trust me you dont need it to know about Recursions) and that is what am about to share. Relax!!!, it easier than you think, it is so simple that you probably overlooked looking at Recursions that way. (next time you have a problem, try thinking about it while taking a bath, there is something in the water that makes the solution flow intuitively. If I and Archimedes can do it, you can also do it)
I would start with an examples - I will write in python because my little sister who knows nothing about programming can read and understand python.
Let create a methods called method that computes factorial.
when factorial(4) is invoked on line 7, it executes the piece of code from 1 - 4 and waits to for the next factorial to execute before returning. It is very important you repeat this statement again, I will write it out so read aloud - "when factorial(4) is invoked on line 7, it executes the piece of code from 1 - 4 and waits to for the next factorial to execute before returning". Good!!!!
factorial() is passed in with the value 4, as it reaches line 5, it makes another call to factorial() passing in a value of 3.
It does the same thing such that when "n" finally gets to zero, it returns 1.
The point here is that method calls that occur within the factorial method execute as subroutines.
When some method or code executes inside another method or code block, the one that executes inside is the routine - a sub routine - of the outer one. permit my verbosity and see code [doofoo() and addfoo()] below
Just like you will normally have a method execute within another method like below.
- #baz is a global variable - something that is outside the methods in this case
- baz = 0
- #some extra code if you want
- return baz
Therefore, before the parent method e.g dofoo() [that is the method with the initial call] can be said to have finished executing, all subroutines e.g addfoo() must finish executing.
Hence taking a recursive example
- '''This is what happens when line 7 above is called'''
- '''line 4 of factorial(3) reaches this line and waits for factorial 4 to finish executing meanwhile 4 is still waiting for 3'''
- '''line 4 of factorial(2) reaches this line and waits for factorial 1 to finish executing meanwhile 4 is waiting for 3 and 3 is waiting for 2'''
- '''line 4 of factorial(1) reaches this line and waits for factorial 0 to finish executing while others above are still waiting'''