It implies recursion, pattern inside of pattern. Self-similarity is symmetry across scale. The base cases for this problem are pretty simple… Hanoi(n - 1, helper, source, target) #moving tower of size n-1 from helper to targetįeel free to go through this entire section once more to digest it, because it’s pretty mentally intensive if you aren’t yet used to thinking this way. Target.append(source.pop()) #appends the last disc from source, to target If source: #checks whether source is empty or not #moving disk from source peg to target peg Hanoi(n - 1, source, target, helper) #moving tower of size n - 1 to helper: Sub-Problem: Moving tower of n – 1 discs from Source to Helper, then moving last disc to Target Problem: Moving tower of n discs from Source to Target So here, in the Tower of Hanoi problem (yeah, that’s the official name), we have: Sub-problem (which is a Problem with a smaller input) We can of course, figure it out by hand as above, but what’re we learning recursion for then?Ī quick recap of the divide-and-conquer method: We now need to solve the problem for n = 7. In fact, we can prove by mathematical induction, that the least number of moves required to solve a tower of n discs is:Ĭlick here if you’d like to see the proof for yourself. Notice anything similar to the previous case? Observe that in Step 3, we have a tower of n – 1 = 2 discs, on Helper now. In Step 1, notice how after we shift the 1st disc to Helper, we have a tower of n – 1 = 1 disc, on Helper. Let’s assume there to be n number of discs, and we’ll be moving the tower from source to target using the helper rod: It can be put on another rod, only if that rod is empty or if the uppermost disk of that rod is larger than the disc being moved. Only the uppermost disk from one rod can be moved at once.ģ. His Dad challenged him to a game, where the objective was to transfer all the discs to another rod, obeying the following rules:Ģ. Baby Algosaurus had a toy with 3 rods and 7 discs. Once upon a time, in the Cretaceous Era, there lived a family of Algosauri in a land far, far away. Let’s take another classic example to hit the point home. Lo and behold, you just learnt recursion. Result = fibo(n-1) + fibo(n-2) #Feeding the 'output' right back into the input function This is also known as the divide-and-conquer paradigm of algorithms, where we segregate a problem into smaller sub-problems, and finally into a simple base case.įinal code for Fibonacci numbers? def fibo(n): So, let’s define Fibonacci numbers in terms of Problems and Base Cases. Notice how this is a recursive definition? Let’s break it down into a recursion tree. You’ll notice that the nth Fibonacci number, after n = 0 and n = 1, is the sum of the previous two Fibonacci numbers. No article on recursion is complete without talking about Fibonacci Numbers.įibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, 21… Sub-problem (which is Problem with a smaller input)īase Case (a Problem with a constant output) While Algosaurus was singing (growling?) his heart out, his mic picked up the output of the surrounding amplifiers, and fed it right back into the input.Īlthough the above example doesn’t reduce to a meaningful output, rather it results in a stack overflow (the screeching sound), this is the essential idea of recursion. …is rudely interrupted by a loud screeching sound from the amplifier. He growls into the mic as he descends into the chorus and… Evidently Photoshop isn’t exactly my strong suit. He goes to a concert venue with a poorly-designed audio system and starts off with his smash-hit song “Rock Tore My World Apart”. “Recursion is a method where the solution to a problem depends on the solutions to smaller instances of the same problem.”īut it still takes an “Aha! Moment” to get an intuitive grasp on it, which is why I’ll finally take a stab at it.Īs usual, we have three levels, so switch to them as you see fit:Īlgosaurus coincidentally happens to be part of an obscure death metal band you’ve never heard of. Sure, we all know the textbook definition: Recursion is possibly one of the most challenging concepts in Computer Science to get the hang of, and something which has fascinated me for a very long time.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |