Understanding Recursion (Through Pain)

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:

1. 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 the word[2] character prepended and the n = 4 case has the word[3] one, etc.
2. 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:

1. We have a function that works correctly for the cases when n <= 4 and
2. 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:

1. Split the original string into two parts: a substring of length 3 and the last character
2. Call the reverse function on that substring, because we know that it works correctly for the n = 3 case and
3. 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();