JavaScript 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();
// ...
}
Code language: JavaScript (javascript)
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();
}
}Code language: JavaScript (javascript)
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);
Code language: JavaScript (javascript)
This countDown(3) shows only the number 3.
To count down from the number 3 to 1, you can:
- show the number 3.
- and call the
countDown(2)that shows the number 2. - 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);
Code language: JavaScript (javascript)
This countDown(3) will run until the call stack size is exceeded, like this:
Uncaught RangeError: Maximum call stack size exceeded.Code language: JavaScript (javascript)
… 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);
Code language: JavaScript (javascript)
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);Code language: JavaScript (javascript)
Error:
Uncaught TypeError: countDown is not a functionCode language: JavaScript (javascript)
How the script works:
- First, assign the
countDownfunction name to the variablenewYearCountDown. - Second, set the
countDownfunction reference tonull. - Third, call the
newYearCountDownfunction.
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);
Code language: JavaScript (javascript)
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);
}Code language: JavaScript (javascript)
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.