There are many posts on the concept of recursion in computer science as well as tutorial examples of implementation in various languages. What I want to write about is (perhaps not as useful) how I came to learn about recursion and why I think it's one of the most beautiful concepts in computer science.
I learned about recursion in my 1st year of a computer science curriculum in undergrad. It of course involved implementing Fibonacci sequence at first. But then I learned about Tower of Hanoi game as a way to visualize why the idea of recursion is so powerful. For those not familiar, the game involves 3 pegs and disks of varying circumference. The objective is to move all disks from say Peg 1 to Peg 2 while using Peg 3 as a temporary placeholder for the disks. The only rule is that you must place a smaller disk on top of a larger disk at all times on all pegs.
You can play the game online to get the idea, it's fun :)
The number of moves required to solve a 3 disk game is 7. For 4 disks it's 15 and 5 disks it's 31. The number of moves roughly doubles with each additional disk. So we can easily imagine the number of moves getting out of hand, in terms of being able to keep everything in our head while solving the game manually. And yet, this is the easiest game of solve and get it right each time. Thanks to the concept of recursion:
Solving a 4 disk game is exactly the same as solving a 3 disk game. This is how. Assume the goal is to move all disks from Peg 1 to Peg 2. You start by moving the top 3 disks from Peg 1 to Peg 3 (and you already know how to do that). Then move the last (largest) disk from Peg 1 to Peg 2. Then move the top 3 disks from Peg 3 to Peg 2 using the exact same process you used to move them from Peg 1 to Peg 3. Easy right! And here is the mind blowing part, this exact same process applies to any number of disks. You can move 50 disks, 100 disks! (of course may take a some hours).
The reason recursion is not only powerful but beautiful is because it holds some simple wisdom. Break the problem down into a slightly smaller problem and imagine how you'd solve this problem if you already knew how to solve the smaller problem. Pair this with some ground level knowledge (i.e. how to move 1 or 2 or 3 disks) that is trivial to get right, you can solve anything.
There are parallels of recursion with the concept of proof by induction in number theory as well as NP complete problems in computational complexity theory. More on that some other time!
Top comments (0)