Recursion for Dummies
You’re not a dummy! But wouldn’t you like recursion explained to you in simple English? Luckily I speak both Nerd and English, so I can translate. If you’re just learning programming, it might seem daunting to try to tackle recursion, but 1) it’s really cool 2) it will help you solve some problems more efficiently and 3) it’s good to stretch your brain!
Recursion in it’s simplest definition is a program that calls itself, either directly or indirectly. It’s related to the mathematical principle of induction. Did I lose you already? Don’t worry, we won’t go too far into the specifics, but induction is a way of proving things in Math, often explained using an analogy of a ladder.
Suppose I wanted to convince you I had an infinitely tall ladder. I would start by proving that the first rung exists; this is called the base case. Then I would prove the inductive step, assuming some other rung exists, we can prove that the next higher rung also exists. In this way, you can prove that all the rungs are there, because of something called the rule of inference.
For our purposes, we sort of need to work backwards. We know that our ladder exists, we’re trying to write a program to climb down the ladder and then stop at the bottom. Say you want to write a program that adds a dash in between each character of a string. What would the base case be? A string of length 1 (e.g. ‘H’). We don’t need to add a dash because it’s only one character. So that will be our endpoint and we’ll just return whatever string has been entered.
What about all the other cases? We can think of each rung of the ladder as a single step closer to our end goal. Each time, we want to take a single character off the string and add a single dash. So if the length of our string is greater than 1, take the first character, add the dash, and then return that PLUS call the function again with whatever’s left over. To make it easier, think about what’s being return each time the function runs if we have a string like ‘Hello world!’ The first time? ‘H-‘, 2nd time? ‘e-’, then ‘l-’ and so on, until finally the bang! (which is our base case), and therefore returns only ‘!’ The output to your console will simply be the final concatenated version ‘H-e-l-l-o- -w-o-r-l-d-!’
Look at how elegant that solution is. If we had solved this problem with a for loop, it would still work, but it wouldn’t be as clean, and once you get used to writing and understanding recursive programs, you might even find a solution like this is more readable. Plus, there are some problems that are particularly well-suited to recursion (e.g. the triangle problem and the Towers of Hanoi.) If you want to learn more, you can check out this video from Computerphile explaining the factorial problem or this video explaining how to break up computer programming problems into simpler parts. It gets into recursion around 5:09 and will blow your mind with the Towers of Hanoi problem at 8:35!
