Recursion, it just works

This article will cover the basics of recursion. Introduce you to a general approach to solving recursion problems —as hinted in the title. We'll use several examples (in ascending difficulty) to demonstrate that approach in practice.
Before starting, we'll have to address the elephant in the room, which is the mindset of most people when starting to learn about recursion.

Having the right mindset

Programming isn't happening in a vacuum, people who start learning to code will (or already have) heard phrases like:

Recursion is evil.

Wait till you reach recursion, that's really hard.

Learning a new subject with such a mindset can significantly hinder the learning experience.
Having an open mind and ditching all prejudice is extremely important when approaching a problem or trying to learn something new.
So before you continue to read the rest of the article, try to forget about things you've heard before regarding recursion and try to have a clear and open mind.

Recursion

Definition

Before we tackle recursion, we need to have some common ground about what we mean when we say "recursion".
Let's look at the following simple definition of recursion (source):

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

Now that we have the definition, we can start to unpack and try to understand what it means.

To understand the definition better, we will use the following problem as an example:

Write a function that accepts an array of length n, which contains numbers as an input and returns the sum of its elements.

Although this problem is very basic it will help us understand the definition with ease (we'll tackle a bit harder problems afterward).

Non-recursive solution

A simple, straightforward solution will be to use a basic for loop:

function sumOfArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length ; i += 1) {
    sum += arr[i];
  }
  return sum;
}

Let's assume we have been given a function sumOfPartialArray (hypothetical function, assume it works as defined), which will accept an array as an argument and return the sum of all of the elements except the first element, for example:

const arr1 = [1,2,3];
const arr2 = [2,5,8,1];
console.log(sumOfPartialArray(arr1)); // output: 2+3 = 5
console.log(sumOfPartialArray(arr2)); // output: 5+8+1 = 14

We can use that function to simplify our solution a bit:

function sumOfArray(arr) {
  const firstElement = arr[0];
  return firstElement + sumOfPartialArray(arr);
}

This weird solution will be useful soon enough.

Recursive solution

Let's try to solve the problem using a simpler version of itself (as described in the definition).
One way to do so is by trying to use a solution to a "smaller" problem to solve our original problem.
We can take out the 1st number from the array, and now we have an array of size n-1.
If we could sum the remaining n-1 elements, we can add the number we took out, add it to the sum and that will solve our problem. But summing an array of n-1 elements is the same problem as we had before. It only has one element less.
We've managed to solve the problem using a simpler version of itself!
However, we still need to solve the simpler version.
We can continue this process (of taking out the 1st element and trying to solve the problem for a smaller array), and eventually, we'll have an array of size 0, which we know how to sum. The sum is just 0 (no elements).
That's also where our process will stop (we can't let it go indefinitely).
That's what we call a base case, that's the simplest version of the problem, it's the version that we know how to solve.
By having a solution to the base case, we also have a solution to the case of an array of size 1, as all it needs is the sum of the smaller array (empty array, sum 0) and the 1st element.
This logic can be applied to the cases of arrays of bigger sizes, up to our original problem with an array of size n.
This process defines recursion: looking for a solution to a progressively smaller problem (the recursive step) until we reach the base case, at which point answers are 'bubbled' back up.
visual representation

Let's try to express our verbal solution in code:

function sumOfArray(arr) {
  const firstElement = arr[0];
  // Now we need to calculate the sum of
  // the remaining n-1 elements
  ...
}

Before we implement the
That looks very similar to our non-recursive solution...
What if we use the sumOfPartialArray in the recursive version too?:

function sumOfArray(arr) {
  const firstElement = arr[0];

  return firstElement + sumOfPartialArray(arr);
}

What exactly does sumOfPartialArray do? It calculates the sum of all of the elements of the array except the 1st one, or in other words, calculates the sum of n-1 last elements of an array. But that's precisely what our sumOfArray will do if we just call it with a different input:

// will call our recursive function with a copy of the
// array without the first element
sumOfArray(arr.slice(1));

We can now replace sumOfPartialArray with sumOfArray and adjust the array:

function sumOfArray(arr) {
  // take the first element
  const firstElement = arr[0];

  return firstElement + sumOfArray(arr.slice(1));
}

Now we have a recursive function (a function that calls itself) and a recursive solution.
Well, that's almost true. The current version (theoretically) won't stop running, as it will keep calling itself without anything to stop it. That's where our base case steps in. That's the case in which we will stop making recursive calls and start returning the answer backward, as we know the solution to our base case:

function sumOfArray(arr) {
  if (arr.length === 0) return 0;
  // take the first element
  const firstElement = arr[0];

  return firstElement + sumOfArray(arr.slice(1));
}

Finally, we have a working recursive solution!

The step of using sumOfPartialArray could've been skipped. If we just assumed that sumOfArray is working.
To understand the last sentence better, let's take the following problem:

Write a function that calculates the factorial of a positive integer.

factorial of number n is calculated by taking the product of all positive integers which are less or equal to n
You can take a moment to try and write a recursive solution on your own before moving forward.

function factorial(n) {
  // We will just assume our function works, so we'll ask for the solution for the smaller problem
  return n * factorial(n-1);
}

And we can't forget the base case. Which is a must to make it work:

function factorial(n) {
  // 0! is also 1
  if (n <= 1) return 1;
  // We will just assume our function works
  return n * factorial(n-1);
}

The main thing to take from this example is that we didn't trouble ourselves with "How will our solution work?" rather we've assumed it just works and used it to solve our general case.
We solved two examples so far considered easy. And usually, those are the examples seen in other articles/tutorials about recursion. Then, the learner tries to solve a harder problem and feels lost.
So let's take a harder problem and try the same approach (to try and understand it better):

• Assume your function works to solve the problem for a "smaller problem" and use that solution to solve your current problem.
• Add the base case. Some prefer to start with the base case. Both approaches are fine.

Subset Sum Problem

Implement the function isSubsetSum(array, sum), which accepts an array and a sum, and determines if the array contains a subset such that the sum of the elements is exactly to the given sum.

You can take a moment to try to solve it on your own if you wish.
This problem introduces another common way to solve recursive problems. We check if there's a solution by including the given element and by excluding it.
We again assume our isSubsetSum works and think what's the smaller problem in this case.
If we take our first element and try to see if the remaining array has a sum that equals to sum - array[0], then we find an answer, which is simply that sub-sum including the first element.
On the other hand, there's a chance that there's a solution that doesn't include our first element.
And that covers all the possibilities (an element is part of the sum or it's not, there's no in-between).
So we found a similar smaller problem now let's see it in code:

function isSubsetSum(array, sum) {
  // slice(1) will return a shallow copy of arr without the 1st element
  const subArray = array.slice(1);
  // Check if there's a solution with the first element
  const withFirst = isSubsetSum(subArray, sum - array[0]);
  // Check if there's a solution without the first element
  const withoutFirst = isSubsetSum(subArray, sum);

  // Will return true if there's a solution with at least
  // one of the options
  return withFirst || withoutFirst;

Simplified version:

function isSubsetSum(array, sum) {
  return isSubsetSum(array.slice(1), sum - array[0]) || isSubsetSum(array.slice(1), sum));
}

There's also the base case to take care of. There are two possibilities here:

1. Sum is 0, there's a solution, taking no elements (similar logic to our sumOfArray problem).
2. The array is empty, and the sum isn't 0, no more elements to try --no solution. So by adding the base case to our solution:

function isSubsetSum(array, sum) {
  if (sum === 0) return true;
  if (array.length === 0) return false;
  return isSubsetSum(array.slice(1), sum - array[0]) || isSubsetSum(array.slice(1), sum);
}

Conclusions

As you've seen, by just assuming that our recursive function works, we managed to focus on solving the problem using the solution of the sub-problem. Understanding our recursive function's behavior at every step is unnecessary and can be burdensome. In essence, our solution follows the same process for each step (remember the definition), except for the base case. After addressing the general case, we only have to add the base case, which is unique.

Disclaimer

I must make an important disclaimer: this article won't and cannot teach you how to solve every possible recursion problem. It gave you a general way of thinking when facing recursion problems and some tools to handle them.
Therefore, I strongly encourage you to try and solve some recursion problems on your own. This active learning process is essential to ensure you understand the subject.