Diving deep - Recursion by Intuition.

 I will assumes that you have heard of recursions and know a little or more on coding, better said - functions, methods or a code blocks.

Okay, having established a basis, lets talk about one of programmers nightmares - Recursion.
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.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
factorial(4)

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.

1. #baz is a global variable - something that is outside the methods in this case
2. baz = 0
3. def dofoo(n):
4. #some extra code if you want
5. 
   
6. bar = addfoo(n)
7. print bar
8. 
   
9. #some extra code if you want

1. def addfoo(value):
2. baz = value + 3  
3. return baz

1. dofoo(5): '''This line executes, while executing, it calls addfoo(5) and
2. waits till addfoo is done executing. addfoo returns baz and 
3. assigns it to bar. Line 7 of dofoo() prints bar as 8'''
4. print baz #prints 8

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

1. def factorial(n):
2. if n == 0:
3. return 1
4. else:
5. return n * factorial(n - 1)
7. print factorial(4)
9. '''This is what happens when line 7 above is called'''
10. factorial(4):
11. if n == 0:
12. return 1
13. else:
14. return 4 * factorial(4-1)==>factorial(3): '''line 14 of factorial(4) reaches this line and waits for factorial 3 to finish executing'''
1. if n == 0:
2. return 1
3. else:
4. return 3 * factorial(3-1)==>factorial(2): '''line 4 of factorial(3) reaches this line and waits for factorial 4 to finish executing meanwhile 4 is still waiting for 3'''
1. if n == 0:
2. return 1
3. else:
4. return 2 * factorial(2-1)==> factorial(1): '''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'''
1. if n == 0:
2. return 1
3. else:
4. return 1 * factorial(1-1)==>factorial(0):'''line 4 of factorial(1) reaches this line and waits for factorial 0 to finish executing while others above are still waiting'''
1. if n == 0:
2. return 1 '''Now n == 0 and factorial(0) will give back the number 1 to factorial(1)'''
3. else:
4. return n * factorial(n-1) ==>
5. else:
6. return 1 * 1 '''Therefore factorial(1) returns 1* 1 = 1
5. else:
6. return 2 * 1 '''Remember factorial(1) returned 1. Now factorial(2) is returning 2 * 1 = 2'''
5. else:
6. return 3 * 2 ''' factorial(3) returns 6'''
15. else:
16. return 4 * 6 '''finally, Our initial call factorial(4) which has been patiently waiting returns 24
18. print factorial(24) #then completes execution an outputs 24

Think of it as a better approach of writing this which appears readable.

def factorial(n):
    val = 1
    while n >= 1:
        val = val * n
        n = n - 1
    return val
 
print factorial(4) #which executes as 4 * 1 * 3 * 2 * 1 

Well that's it.