Understanding Recursion in Javascript

Recursion simply refers to a situation where a function calls itself. The function continuously calls itself (usually with different inputs) until a condition, referred to as a base case is met.

The Parts of a Recursive Function

All recursive functions usually consist of 3 parts.

• A base case to terminate the function's execution

• The body of the function

• The recursive call

Let's see these three parts in an example function:

Creating a Recursive Function

function recursiveCountDown(n) {
  // the base case
  if (n < 0) {
    return;
  }

  // the body of the function
  console.log(n);

  // the recursive call
  recursiveCountDown(n - 1);
}

recursiveCountDown(5); // => prints 5 then 4 then 3 then 2 then 1 then 0

The function above recursiveCountDown prints numbers starting from n down to 0. Let's take a closer look at how it works.

• The function first checks whether the argument passed to it is less than 0 (the base case). If it is, it returns out of the function and terminates execution.

• If the number passed is not 0, the function logs the number to the console.

• After logging the number to the console, the function then calls itself again with an argument of n - 1.

• This process is repeated until the number passed to the function is less than 0 ( the base case ).

But this is a simple example. Let's try a different example, but this time, a function that calculates the factorial of a number n (represented by n!). The factorial of a number n is simply the product of all positive integers less than or equal to n (e.g 4! would be 4 * 3 * 2 * 1). We will create two versions, an iterative version (using a loop) and a recursive version.

// iterative version
function iterativeFactorial(n) {
  // result is set to 1 intially;
  let result = 1;

  // loop that carries out the repeated multiplication
  for (let i = n; i > 0; i--) {
    result *= i;
  }

  return result;
}

console.log(iterativeFactorial(4)); // => 24

In the iterative version, we use a loop that continuously multiplies the result variable with i until i is no longer greater than 0. i continuously gets reduced by 1 on each iteration of the loop. We'll now do something similar, but using a recursive function.

// recursive version
function recursiveFactorial(n) {
  //   base case
  if (n === 1) {
    return 1;
  }

  //   recursive call
  return n * recursiveFactorial(n - 1);
}

console.log(recursiveFactorial(4)); // => 24

The recursive version takes a lot less code than the iterative version. Let's dig deeper into how it works.

How Recursive Functions Work

We will try to understand how recursive functions work by analyzing how the recursiveFactorial function we created above works when called.

• recursiveFactorial is intially called with an argument of 4.

• It hits the base case and compares whether 4 is equal to 1.

• Since 4 is not equal to 1, it skips that block and moves to the next statement, the return statement. It returns 4 \ recursiveFactorial(4 - 1) which would be 4 * recursiveFactorial(3)*.

• Since recursiveFactorial is called again, we repeat the entire process.

• The function executes from the top again and compares whether 3 is equal to 1.

• Since 3 is not equal to 1, it hits the return statement and returns 3 \ recursiveFactorial(3 - 1) which would now be 3 * recursiveFactorial(2)*.

• At this point, the return value of the initial call to recursiveFactorial is now 4 \ 3 * recursiveFactorial(2)*.

• Since there is, yet again, another call to recursiveFactorial, we repeat the process.

• The function executes again from the top, this time, comparing whether 2 is equal to 1.

• Since 2 is not equal to 1, it hits the return statement and returns 2 \ recursiveFactorial(2 - 1)*.

• The return statement of the initial call at this point is now 4 \ 3 * 2 * recursiveFactorial(1)*.

• The function once again executes from the top and compares whether 1 is equal to 1.

• Since 1 is in fact equal to 1, this function returns 1.

• The return statement of the initial call to recursiveFactorial is now 4 \ 3 * 2 * 1*.

• This can now be evaluated and recursiveFactorial returns a number, 24.

By looking at a recursive call step by step, we now have a much better understanding of how recursive functions work. The initial call to a recursive function is only completed after all subsequent calls are themselves completed. To understand why this is so, a look into how functions are executed in javaScript will aid us.

The JavaScript Call Stack

The call stack in javaScript is used by the javaScript engine to keep track of functions currently running in a program. The stack works more like a real stack data structure and follows the LIFO (Last In First Out) principle. When a function is called, the functions's execution is placed at the top of the call stack. If the function currently being executed calls another function, that new function is itself placed at the top and the previous function is pushed downwards. Execution of the previous function halts until the new function has completely executed. If we apply this knowledge of how the call stack works to a recursive call, we will see that the initial call of a recursive function would be halted until all subsequent calls are themselves completely executed. This might be a lot to understand at first. If you'd like to read more about the javascript call stack and how it works, check out this article.

Conclusion

This article was a short introduction to what recursion is, how it works and how to create a recursive function to solve a particular problem. I hope this article helped you understand a bit more about recursion and how to apply it in your javaScript programs. Thanks for sticking with me to the end and happy hacking!