Keep Recursion Simple

Break it down to the base case!

A function that calls itself, that calls itself, that calls itself… Recursion can be a tricky concept to wrap your brain around! 😵

Keep it simple

Many people choose a difficult problem as their first attempt at recursion. Often the problem involves advanced data structures like trees. In many ways, this makes sense! These are the types of problems that recursion can make simpler. Recursion is best at solving problems where you can sub-divide it into smaller problems.

My advice is to start by doing the opposite. At least while learning recursion, attempt to solve the simple problems first. Take a problem you would normally solve iteratively and attempt to solve it with recursion. It will be tough at first! With enough practice you’ll learn to recognize situations where recursion can help and you’ll be able to apply your new skills.

Break it Down

If you can handle coding loops, you are capable of learning recursion!

Take a while loop:

while(condition) { /* body */ } 

In this loop we execute the body block while the condition is true.

Rather than a condition to keep running, recursive algorithms reach a point to stop and return. This point is commonly referred to as the base case.

Let’s take an example. Imagine we are counting squares. Start from the top with a count of zero and count one square at a time:

Picture each rectangle above as a call to a function. We execute the Body with new Arguments until we reach our Base Case. At that point we return our final count, 3.

• Body: Remove a Square, Increment Count.
• Arguments: Squares and Count.
• Base Case: No Squares Left.

When you’re writing a recursive solution, keep two things in mind:

1. Each time you call the function, an argument must change. One argument in particular should be changing towards the base case.
2. Establish your base case. Figure out when the recursion ends! Without a place to stop you’ll wind up overflowing the call stack.

Code Example

Let’s think of another simple problem that is normally solved iteratively: summing an array of numbers.

const numbers = [1,2,3];

Solving this iteratively is a cinch!

function total(numbers) {
  let sum = 0;
  for(let i = 0; i < numbers; length; i++) {
    sum += numbers[i];
  }
  
  return sum;
}

What if we wanted to solve this recursively?

Let’s start with numbers [1,2,3] and a sum 0.

A good first step would be to think ahead to our base case. How do we know when to stop? One solution is to remove an element from the array each time we recurse. That way, when the array is empty we know it’s time to stop and return the sum.

Each time we remove the element we can add it to the sum, so we accumulate the total by the end of the recursion!

What would this look like as a JavaScript function?

function total(numbers, sum = 0) {
  // base case
  if(numbers.length === 0) return sum;
  
  // remove an element, add it to sum 
  sum += numbers.pop();
  
  // recurse 
  return total(numbers, sum);
}

Each time the function calls itself, it is added to the call stack. The call stack keeps track of where we are in the program so it knows where to return. Starting from the first function call, the call stack would look like this:

total([1,2,3], 0);
 total([1,2], 1);
  total([1], 2);
   total([], 3);

Notice how the arguments change each time we call total. The numbers are changing towards an empty array, while the sum is accumulating. Each call to total returns the result of the function call inside it, resulting in the final sum being returned all the way up the stack.

Be mindful that pop modifies the original array! Any part of the program holding a reference to the array can be affected.

Now, this isn’t the only solution to solve this problem recursively. Another solution would be to keep an index. This actually works out pretty similar to a loop:

function total(numbers, index = 0, sum = 0) {
  if(numbers.length === index) return sum;
  sum += numbers[index];
  return total(numbers, index + 1, sum);
}

In this case, we don’t modify our array numbers. We increment the index instead. We use that index to read numbers from the array and add them the sum. Once the index reaches the length of the array we return the sum all the way back up the call stack.

total([1,2,3], 0, 0);
 total([1,2,3], 1, 1);
  total([1,2,3], 2, 3);
   total([1,2,3], 3, 6);

See the difference? We’re not modifying the array each time. We’re modifying the index instead. Just like a loop condition, your base case can be anything you choose it to be!

Finally, I’ll provide one more solution:

function total(numbers) {
  if(numbers.length === 0) return 0;
  
  return numbers.pop() + total(numbers);
}

This solution is a bit trickier. Instead of accumulating the sum and passing it down the call stack, we’re adding the number to the return value of each recursive call. Neat, huh?

Ready for Recursion Code Challenges?

Try this Tutorial out from the comfort of your own web browser! 💻

Follow us on Twitter🐦 or join us at ChainShot to go from zero programming experience to blockchain developer!