How Can We Help?

# Recursive Function

## Introduction to the JavaScript recursive functions

A recursive function is a function that calls itself until it doesn’t. And this technique is called recursion.

Suppose that you have a function called `recurse()`. The `recurse()` is a recursive function if it calls itself inside its body, like this:

``````function recurse() {
// ...
recurse();
// ...
}
``````

A recursive function always has a condition to stop calling itself. Otherwise, it will call itself indefinitely. So a recursive function typically looks like the following:

``````function recurse() {
if(condition) {
// stop calling itself//...
} else {
recurse();
}
}
``````

Generally, you use recursive functions to break down a big problem into smaller ones. Typically, you will find the recursive functions in data structures like binary trees and graphs and algorithms such as binary search and quicksort.

## JavaScript recursive function examples

Let’s take some examples of using recursive functions.

### 1) A simple JavaScript recursive function example

Suppose that you need to develop a function that counts down from a specified number to 1. For example, to count down from 3 to 1:

``````3
2
1
``````

The following shows the `countDown()` function:

``````function countDown(fromNumber) {
console.log(fromNumber);
}

countDown(3);
``````

This `countDown(3)` shows only the number 3.

To count down from the number 3 to 1, you can:

1. show the number 3.
2. and call the `countDown(2)` that shows the number 2.
3. and call the `countDown(1)` that shows the number 1.

The following changes the `countDown()` to a recursive function:

``````function countDown(fromNumber) {
console.log(fromNumber);
countDown(fromNumber-1);
}

countDown(3);
``````

This `countDown(3)` will run until the call stack size is exceeded, like this:

``````Uncaught RangeError: Maximum call stack size exceeded.
``````

… because it doesn’t have the condition to stop calling itself.

The count down will stop when the next number is zero. Therefore, you add an if condition as follows:

``````function countDown(fromNumber) {
console.log(fromNumber);

let nextNumber = fromNumber - 1;

if (nextNumber > 0) {
countDown(nextNumber);
}
}
countDown(3);
``````

Output:

``````3
2
1
``````

The `countDown()` seems to work as expected.

However, as mentioned in the Function type tutorial, the function’s name is a reference to the actual function object.

If the function name is set to `null` somewhere in the code, the recursive function will stop working.

For example, the following code will result in an error:

``````let newYearCountDown = countDown;
// somewhere in the code
countDown = null;
// the following function call will cause an error
newYearCountDown(10);
``````

Error:

``````Uncaught TypeError: countDown is not a function
``````

How the script works:

• First, assign the `countDown` function name to the variable `newYearCountDown`.
• Second, set the `countDown` function reference to `null`.
• Third, call the `newYearCountDown` function.

The code causes an error because the body of the `countDown()` function references the `countDown` function name, which was set to `null` at the time of calling the function.

To fix it, you can use a named function expression as follows:

``````let countDown = function f(fromNumber) {
console.log(fromNumber);

let nextNumber = fromNumber - 1;

if (nextNumber > 0) {
f(nextNumber);
}
}

let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);
``````

### 2) Calculate the sum of n natural numbers example

Suppose you need to calculate the sum of natural numbers from 1 to n using the recursion technique. To do that, you need to define the `sum()` recursively as follows:

``````sum(n) = n + sum(n-1)
sum(n-1) = n - 1 + sum(n-2)
...
sum(1) = 1
``````

The following illustrates the `sum()` recursive function:

``````function sum(n) {
if (n <= 1) {
return n;
}
return n + sum(n - 1);
}
``````

## Summary

• A recursive function is a function that calls itself until it doesn’t
• A recursive function always has a condition that stops the function from calling itself.