In this section we will learn what the Recursion is and how it works in JavaScript.

Note: we’re assuming you’re already familiar with the Stack memory.

What Is Recursion?

Recursion is the process of calling a function inside the body of itself.

We know that inside the body of a function, we can call other functions. But one thing that you might didn’t notice is that we can call the function within its body as well! This is called recursion.

What Is a Recursive Function?

A function that is calling itself within its body is called a recursive function.

Recursion at its core is a simple process. All is happening is that a function is calling itself within its body. But if we don’t pay attention, it can easily crash a program!

If you think about it, allowing a function to simply call itself without any precautions, it will create an infinite loop! Basically, the execution engine enters the body of the function and sees another call to the function. So it will run the body of the function again (it sets aside another block of stack memory for the body of the function). This process will occur over and over again until there’s no memory left in the Stack area (Hence the program will crash).

Example: recursion in JavaScript

function multiply(value){
  if (value !=0){
      return multiply(value -1) * value;
  }else{
      return 1;
  }
}
const res = multiply(4);
console.log(res);

Output:

24

How recursion works in JavaScript?

Let’s break this example and see how we got the value 24:

First, the execution engine invoked the call to the `multiply()` function with the value 4.

multiply(4):

The first time we called this function, the assigned value was 4.

Within the body of this function, we have an `if-statement` which is in charge of checking to see if the argument of the function is not zero.

For this call, the result of this condition is true (the argument is 4) and so the body of the `if-statement` will run.

Within this statement, we have the `return` keyword with the expression of ` multiply(value -1) * value`.

In order to resolve the expression, the execution engine needs to invoke the `multiply` function with the value of `value-1` which is basically the `multiply(3)` function.

As mentioned before in the stack&heap section, when a function is called within the body of another function, the execution engine will stop running the first function and will jump into running the body of the second one.

So here the first function call will stop running until the result of the `multiply(3)` function is declared and retuned.

multiply(3):

The first line of this function was to check if the input is not 0, and as you can see, the value is 3, so the condition is true and its body will run.

Within the body of the statement, we have the expression of ` multiply(value -1) * value` which is equal to: `multiply(2) * 3`. So solving the expression, the execution engine will stop running the current function and will jump to run the `multiply(2)` function to get the result of the function call.

multiply(2):

Again, the first line in the function is to check the value of the argument and because this argument is not 0, the body of the `if` statement runs.

The expression in the statement will be: ` multiply(value -1) * value`, which is equal to: ` multiply(1) * 2`. And again, in order to resolve the expression, a call to the `multiply(1)` should happen. (Another block of stack memory will be set aside for this call)

multiply(1):

In this call, because the value of the argument is still non-zero, the body of the `if-statement` will run and so we will have this expression within the statement: ` multiply(0) * 1`.

Again, to solve the expression, another call to the `multiply()` function with the value of 0 should happen.

multiply(0):

This time because the value of the function (argument) is 0, the condition of the `if-statement` won’t run and so the body of the `else` statement is the one to run instead.

Within the body of this statement, we have the `return 1` which will cause the `multiply(0)` to terminate with the value 1 as its final result.

So now one function `multiply(0)` resolved, and it is off the stack.

Note: so far we started with `multiply(4)`, `multiply(3)`, `multiply(2)`, `multiply(1)`, and here `multiply(0)`. Basically, we have a stack of 5 functions with the `multiply(0)` is off the stack now, the remaining blocks in the stack will be 4.

Basically, every time a function resolves, it will become off the stack.

Back to the multiply(1):

The function was at `return multiply(0) * 1` statement when the call to the `multiply(0)` happened. Now, because the result of the call is clear, the function call will be replaced with its value and the final expression becomes: `1*1`.

So the value that `multiply(1)` will return is 1.

Back to the multiply(2):

We know that the call to the `multiply(1)` happened within the body of the `multiply(2)` in the expression of: ` multiply(1) * 2`. So now that the value of the `multiply(1)` is clear, the function will be replaced with its returned value, which is 1 and the final result of this expression at this point becomes 2. (`1*2`)

Back to the multiply(3):

The call to the `multiply(2)` happened within the body of the `multiply(3)` in the expression of: ` multiply(2) * 3`. And now that the result of the call to the `multiply(2)` is clear, this expression can be resolved as well.

So the final expression becomes: ` 2 * 3` which results 6 and that’s the value that will be returned to the caller function.

Back to the multiply (4):

This function was the first call, and it has the expression: ` multiply(3) * 4` that caused the call to the `multiply(3)`.

Now that the result of the `multiply(3)` is clear. This expression can also be resolved.

So the final expression becomes: `6 *4` which is equal to 24. And the value 24 is the one that will be assigned to the variable `res`.

In the last statement of this program, the value stored in the `res` variable is sent to the browser’s console and after this, the work of the program is done.

Infinite recursion in JavaScript

As you saw at the beginning of this section, infinite recursion is the process of a function calling itself without any break point, which will lead to stack overflow, eventually!

Note: the stack area in the memory has a limited space! So if you push too many calls into this area, eventually it will run out of space (hence the word overflow) and we will get an error and the crash of our program that comes next!

Example: creating infinite recursion in JavaScript

function recursiveFunction(){
  recursiveFunction();
}
recursiveFunction();

Output:

Uncaught RangeError: Maximum call stack size exceeded

As you can see, the function is calling itself infinitely and, because of the limits on the Stack memory; the program crashed just a few milliseconds after running.

Stop condition in JavaScript Recursion

Now, in order to stop a recursive function from overflowing the memory, we use a breakpoint (a stop condition) in the body of the function itself where the recursion will stop and no other call to the function will happen.

This stop condition could be created using a simple if statement, for example!

Example: break condition in JavaScript recursion

let num = 0; 
function recursiveFunction(){
  while (num <100){
    num++; 
    recursiveFunction();
  }
}
recursiveFunction();
console.log("The function called itself 100 times and then stopped!");
console.log(`The final value of the num variable is ${num}`);

Output:

The function called itself 100 times and then stopped!
The final value of the num variable is 100

As you can see, this time we’ve used the `while` loop and the variable `num` to create a breakpoint and stop the function from executing itself infinitely.

Note: The important point to remember is that you should always create a breakpoint in your recursive function in order to make sure your program won’t crash because of the StackOverFlow error.

What is StackOverFlow error in JavaScript?

The Stack in the memory has a limited memory size. So if we invoke many functions at the execution time, at some point the available space in the stack memory will end and hence it won’t take any more function! That’s where the execution engine will throw an exception which is known as the StackOverFlow.

You’ll see this error specially if you create a recursive function that infinitely calls itself.

Example: throwing StackOverFlow error in JavaScript

function sayHi(name){
   sayHi();
 }
 sayHi();

Output:

Uncaught RangeError: Maximum call stack size exceeded

After running this program, we got an error which is saying that the stack overflowed!

Let’s see what happened:

The first time execution engine ran the `sayHi()` function, a memory space in the stack is set aside for this function and the instructions inside it executed one at a time.

Here, the only instruction is to call the function itself! So before calling the function again, a memory space in the stack is allocated to the `sayHi()` function again and now the instruction in the body of this function will be executed.

We know that the only instruction in this body is to invoke itself again!

To the eyes of the computer, there’s no difference between a function calling itself or calling another function. Basically, at this stage, another memory space in the stack is set aside for the `sayHi()` function and the execution engine invokes the body of this function for the third time!

Because inside the body of the `sayHi()` function there’s nothing but calling the `sayHi()` function again, inside the stack every time the call happens, a new memory space will be allocated to that `sayHi()`. This process will repeat itself to the point where there will be no stack memory space left and the program will crash.

That’s why we’ve got the `Stack overflowed` error.

Notes on JavaScript recursion:

1. Recursion is about simplifying a process. For example, if someone asked to add a range of numbers together (for example 0 to 100), we can simply use recursion.
2. Recursion is somewhat difficult to understand at first, but if you keep running other types of examples, it’ll soon get easy to understand.
3. If you don’t pay attention, a function can call itself infinitely. Of course, because the memory is limited, a function might call itself multiple times and then the program simply crashes because it ran out of memory, which also known as `Stack overflowed`.

So make sure there’s a condition in your function that finally stops letting the function to call itself.