So, what is recursion?
To put it in plain English, recursion is a process when function calls itself repeatedly. The philosophy behind recursion is to take a complex problem and deconstruct it down to trivially solvable pieces.
As an example, say we want to reverse an n
-sized string.
We can start chipping away at this gargantuan problem by solving the simplest cases first, namely when n = 0
and n = 1
.
We'd get a function that looks something like this:
const reverse = (word) => {
return word;
}
Indeed, when a string has 1 or 0 characters, it is already reversed so we simply return it. Job well done.
Now, what happens if we have a string that is 2 characters long? We can simply swap those characters:
const reverse = (word) => {
if (word.length <= 1) return word;
return `${word[1]}${word[0]}`;
}
Indeed, the resulting function works when n = 0
, n = 1
, and n = 2
. However, this is not enough. Let's follow our approach further and handle the n = 3
case as well:
const reverse = (word) => {
if (word.length <= 1) return word;
if (word.length === 2) return `${word[1]}${word[0]}`;
return `${word[2]}${word[1]}${word[0]}`;
}
With this change our function covers the cases: n = 0
, n = 1
, n = 2
, and n = 3
.
Ok, now we'll do something different, right? Wrong. We'll repeat the same thing for the n = 4
case:
const reverse = (word) => {
if (word.length <= 1) return word;
if (word.length === 2) return `${word[1]}${word[0]}`;
if (word.length === 3) return `${word[2]}${word[1]}${word[0]}`;
return `${word[3]}${word[2]}${word[1]}${word[0]}`;
}
Hmm, what is the pattern that emerges here? If we look closely at the return statements we'll see that:
- After each step the sequence of the chained characters is the same, except there is an additional character prepended to them. Indeed, the
n = 3
case has theword[2]
character prepended and then = 4
case has theword[3]
one, etc. - Every new string that is returned has the first character of the original word on the rightmost position and the last one - on the leftmost position.
Yeah... that's interesting (not really), but so what?
Let's recap what we have at this point:
- We have a function that works correctly for the cases when
n <= 4
and - We observed two patterns that emerged while we were developing our function
Let's capitalize on the pattern #1 (I'll leave the pattern #2 for the reader to explore on his / her own). If we examine the function closely, we'll see that the n = 4
case repeats the job that is done by the n = 3
case and prepends the last character to the resulting string. Now, the n = 3
case does the same thing, it repeats the job that is done by the n = 2
case and just prepends the last character to it... you got the idea.
This leads us to the following thought - why duplicate the work that's already being done by a previous case? Let's delegate this work to it instead! In other words, for the n = 4
case let's:
- Split the original string into two parts: a substring of length 3 and the last character
- Call the
reverse
function on that substring, because we know that it works correctly for then = 3
case and - Prepend the last character to the resulting string
The refactor will leave us with something like the following:
const reverse = (word) => {
if (word.length <= 1) return word;
if (word.length === 2) return `${word[1]}${word[0]}`;
if (word.length === 3) return `${word[2]}${word[1]}${word[0]}`;
const lastCharacter = word[word.length - 1];
const substring = word.substring(0, word.length - 1);
return `${lastCharacter}${reverse(substring)}`;
}
What keeps us from applying the same logic for the cases n = 3
and n = 2
since they operate by the same principle as well? Let's do this:
const reverse = (word) => {
if (word.length <= 1) return word;
const lastCharacter = word[word.length - 1];
const substring = word.substring(0, word.length - 1);
return `${lastCharacter}${reverse(substring)}`;
}
Voilà.
We're left with a function that we know will work for a string of length n
, because it will work for the string of length n - 1
. Now the case n - 1
will work because the n - 2
case will work, which in turn will work because the n - 3
case will also work...

... because the n = 2
case will work because the n = 1
case will work, whew.
I hope this post helps explain the thought process of approaching a problem from a recursion standpoint.
Please note, that we didn't cover how the function would run on each step, because this detail was irrelevant to solving our problem.
if (!understood) reread();