Recursion: One Step at a Time
The definition of recursion made sense to me long before its application. Anyone who has spent time in a bootcamp or a CS program knows there is no shortage of resources online that clearly state and define what recursion is: Recursion is when a thing is defined by itself or its type. In nature we might envision this as a fractal.
In computer programming, recursion is when a function calls itself — until it doesn’t. This, at surface level, feels simple.
There are only three steps involved in any recursive function — but they are all vital:
1. Base Case — This is the line of code that lets the function know when to stop.
2. The irreducible direction toward the Base Case — More on this in a moment.
3. Recursive Call — The function calling itself.
For me, the disconnect came once I tried implementing my own recursive function to solve a problem. I think most programmers can vouch that there may often be a disconnect between understanding what a line of code is doing and understanding how to conceptualize and implement that code when initially confronted with the problem.
Standing on one side of the river and asking yourself to build code that gets you to the other side can feel vast. Recursion asks you only worry about taking that first step. And then repeating that step. There is faith involved.
Let’s flesh out the analogy above. In the proposed problem, we need to move from one side of the river to the other. There is a definitive starting location and a definitive ending location. The destination and stopping point of a recursive problem is always the Base Case (i.e., the other side of the river).
This is our first step: If you are on the destination side of the river, take no more steps.
Makes sense, right? Second, we need that irreducible bit of code that takes us one position closer to our Base Case. In our current predicament, we can say: Take one step toward the other side of the river.
Now that we have defined our destination (the Base Case) and implemented the irreducible line of code that propels us one part closer toward that destination (taking one step), we now need to implement our Recursive Call (that is, the function calling itself): Get to the other side of the river.
This line will repeat itself until we have reached our Base Case (the other side of the river) at which point it will stop. Again, it requires a bit of programming faith: that one step at a time is enough to get you to the desired location.
So, let’s apply this to a common and simple recursive exercise in JavaScript. Imagine on day one of your new job at High-Tech Global Corps, your boss desperately needs you to find out whether or not “tacocat” is, indeed, a palindrome.
You start with the word “tacocat” and a conceptual definition of what a palindrome is: is this word identical from front to back? How can we build a function that will simultaneously check the first character and last character of a string?
The conditional might look something like this:
Breaking this down is simple enough, right/ If the first letter is = to the last letter, return isPalindrome with the first and last characters removed. However, if the first and last letter are not strictly equal, return False — end of function, bing bang boom.
This logic will repeat itself until it reaches the Base Case.
In the example for this problem, the Base Case would be if the length of the word reaches 1 while still maintaining true.
Running this example through Python Tutor you can easily visualize how this recursive function is acting.
As you can see, the function removes the first and last characters and compares their values until it either reaches the Base Case or returns False.
I hope this helps. Remember, recursion requires one initial step in the right direction.
