Simple Recursion

A significant chunk of Hack Reactor’s pre-course work involves rebuilding several javascript functions that utilize recursion. The first time I saw recursion I had a very difficult time mentally wrapping my mind around it. My brain exceeded its call stack size. After receiving valuable instruction from teachers here at Hack Reactor and having practiced recursion a ton I now understand why recursion is so difficult to grasp. I have also learned how easy it could have been to learn recursion. For any who are confused I hope this helps.

Why is recursion initially so difficult to understand? #

The reason why so many people have a hard time understanding recursion is because they approach it the wrong way. People will often try to mentally follow their code through each line and through each iteration of the recursive function. This approach often leads to confusion and frustration because of how difficult it can be to follow the code. Below are some simple steps that will help you confidently and quickly craft elegant recursive functions.

Trust your code #

If you follow these two steps then your recursive function will work.

Step 1:

Define a solution in terms of a smaller version of itself.

Step 2:

Identify your base case.

Let me explain #

For an example I will use a simple recursive function that returns the factorial of an integer.

The first step is to identify the part of the function that will need to be repeated.

In this case the part of the function that needs to be repeated is the part where the integer is multiplied with the integer one less than itself.
For example, if our integer is 5 then when our function is first called we multiply 5 by 4. In the next iteration of the function we multiply the product of 5 and 4 by 3. In the next iteration we multiply the product of ((5 * 4) * 3) by 2 and so on.

Our code after the first step:

var factorialOf = function(integer) {
    return integer * factorialOf(integer - 1);
}

This code effectively multiplies the current integer by the integer one less than itself. There’s a problem though. Nothing tells this function to stop multiplying its integer by the one less than it. This function will indefinitely multiply its integer by the one less than it. It will go on forever in an infinite loop.

This is where our base case comes in. With our base case we define the point where we no longer want the function to continue to call itself. In this case that is when the integer equals one. The base case breaks us out of the loop, a little like the condition of a while loop.

Here is our base case:

var factorialOf = function(integer) {

  //The base case
  if (integer === 0) {
    return 1;
  }

  //The meat of the function

  return integer * factorialOf(integer - 1);
};

All we need to worry about is whether or not the function will work for a single iteration. Is 5 * 4 what we want? If yes then we define our base case. If our function works for a single iteration and we have a clearly defined base case then our function will work. It’s that simple!

Trust #

If you examine your function and see that it will work for a single iteration, and if you have a clearly defined base case then your function works.

Don’t worry about the intricacies of recursion at first. Simply check to see if your function satisfies these two requirements and then have faith that it will work.