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.
 #baz is a global variable  something that is outside the methods in this case
 baz = 0
 def dofoo(n):
 #some extra code if you want
 bar = addfoo(n)
 print bar
 #some extra code if you want
 def addfoo(value):
 baz = value + 3
 return baz
 dofoo(5): '''This line executes, while executing, it calls addfoo(5) and
 waits till addfoo is done executing. addfoo returns baz and
 assigns it to bar. Line 7 of dofoo() prints bar as 8'''
 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
 def factorial(n):
 if n == 0:
 return 1
 else:
 return n * factorial(n  1)
 print factorial(4)
 '''This is what happens when line 7 above is called'''
 factorial(4):
 if n == 0:
 return 1
 else:
 return 4 * factorial(41)==>factorial(3): '''line 14 of factorial(4) reaches this line and waits for factorial 3 to finish executing'''
 if n == 0:
 return 1
 else:
 return 3 * factorial(31)==>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'''
 if n == 0:
 return 1
 else:
 return 2 * factorial(21)==> 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'''
 if n == 0:
 return 1
 else:
 return 1 * factorial(11)==>factorial(0):'''line 4 of factorial(1) reaches this line and waits for factorial 0 to finish executing while others above are still waiting'''
 if n == 0:
 return 1 '''Now n == 0 and factorial(0) will give back the number 1 to factorial(1)'''

else: return n * factorial(n1) ==>else: return 1 * 1 '''Therefore factorial(1) returns 1* 1 = 1
else: return 2 * 1 '''Remember factorial(1) returned 1. Now factorial(2) is returning 2 * 1 = 2'''

else:  return 3 * 2 ''' factorial(3) returns 6'''
else: return 4 * 6 '''finally, Our initial call factorial(4) which has been patiently waiting returns 24
 print factorial(24) #then completes execution an outputs 24
 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.
No comments:
Post a Comment