A Look Into Recursion

Recursion is a helpful process by which we can make code call itself. Any situation in JavaScript where you would need to iterate, even if you don’t know exactly how many times, you can take advantage of the recursion method. Besides loops, there are tons of other situations we can apply recursion. In this process, you use a function to call itself until you get to the desired case.

One simple example to show would be finding out if a number is divisible by five.

x % 5 === 0 ? true : false;

The same above expression could be written using recursion like so...

function divisibleBy5(num){
  if(num > 0 && num < 5){
    return false;
  } else if(num === 5) {
    return true;
  }

  return divisibleBy5(num - 5);
}

Base Case and Recursive Case

A recursive function consists of two major phases, the base case and the recursive case. It should always start with a base case, which allows for the function to return and exit if certain arguments are passed in or a certain condition has been met. Similar to a loop, this part is necessary if you don’t want to crash your program (In a little bit, I’ll talk more about the call stack).

I would like to re-use the above example to show you that you can have more than one base case.

function divisibleBy5(num){
  // base case
  if(num > 0 && num < 5){
    return false;
  } else if(num === 5) {
    return true;
  } else if(num < 0){
    return 'try again with a positive number';
  }

  // recursive case
  return divisibleBy5(num - 5);
}

Before we wanted two base cases in this divisibleBy5 function because we had two potential outcomes. You can also add additional base cases if you want specific arguments passed in when the function is called.

The second major part of recursion would be the recursive case. This is where you mutate the arguments that were passed in and call the function again. It is worthwhile to note, that if you are using recursion with a collection, you probably want to use nondestructive methods so as not to destroy your data! (i.e., use method .slice() instead of .splice()) You do not have to mutate your data inside the returned function call, but often you may want to. If when making a recursive function, you’re feeling lost as to where to start, it can often be easiest to begin with the recursive case because you know this will be done every time the function calls itself. Then you can come up with an idea of what will be happening to your data on every call, which will often make it clear as to when you need to exit the function(or the base case).

Here we've got another example of recursion, this time getting the sum of all the elements in an array.

function sumOfArray(array, sum = 0){
  // base case
  if(array.length === 0){
    return sum;
  }

  // recursive case
  sum += array[0];
  return sumOfArray(array.slice(1), sum);
}

When using recursion on an array, we always want to work with the first element of the array. Also as mentioned before, we're using the slice() method so as not to destroy the array we pass into the function.

The Call Stack

The JavaScript interpreter, which translates your JavaScript so that your computer understands it, has a mechanism called the call stack. When using loops, you must include an iterator, or your whole program crashes. This concept is similar when using recursion, except now you’d get a “stack overflow” error. Every function call in JavaScript gets added to the top of the call stack, and then anytime the function return is resolved, it gets removed from the stack. The call stack only has so much memory to work with, afterwards it “overflows” and your program will crash. The call stack does have enough memory to the point where this won’t often be an issue unless you forget to update your arguments before passing them through the recursion step.

function sumOfArray(array, sum = 0){
  // base case
  if(array.length === 0){
    return sum;
  }

  // recursive case
  sum += array[0];
  return sumOfArray(array, sum);
}

This would be an example of exceeding the call stack because an iterator was left out. Calling this function, as is, with an array of any length greater than zero will result in an error.
RangeError: Maximum call stack size exceeded

In conclusion,

Anytime you want to iterate through recursion, just create a base case and a recursive case. Also, keep in mind that the call stack does have a limit! Sometimes recursion can even make your code more readable and even potentially cut down the necessary code, now no one has to decipher that loop!