Recursion in JavaScript is a process of invoking itself. A function that calls (invokes) itself is called recursive function.
In other words, a program in which a function invokes itself is called recursion, and the related function is called a recursive function.
A recursive function is a chain of function calls to the same function. It is like the loop with or without a terminating condition. It calls itself, either directly or indirectly, via another function.
A famous example often used to describe the recursion is the calculation of factorial (the factorial for a value of 5 is 5 * 4 * 3 * 2 * 1).
Recursion in JavaScript should use best when we need to call the same function repeatedly with different parameters.
It provides some advantages to programmers, such as to develop the neat and short code and also helps to programmers to avoid loops.
JavaScript Recursion Syntax
The syntax to declare a recursive function in JavaScript that calls itself directly is as follows:
function recursiveFunction(param) {
// function code
recursiveFunction(param);
}
recursiveFunction(arguments);
The above recursiveFunction() is a recursive function that is invoking itself inside the function. It is also possible that recursive function calls itself indirectly.
The syntax to declare a recursive function that calls itself repeatedly indirect is as:
function recursiveFunction1(param) {
// function code.
recursiveFunction2(param);
}
function recursiveFunction2(param) {
// function code.
recursiveFunction1(param);
}
Suppose we have to run recursiveFunction() function in the above code. What would be the result? In this case, the above recursiveFunction will execute indefinitely. Due to which the web browser may crash.
How to stop Recursion in JavaScript?
While defining recursive function, it is necessary to specify a termination condition. If we do not specify such a condition, then an infinite “function” call may occur.
For this reason, we need to set a condition to terminate the recursion. This condition is called base case or stopping point. Base case is a condition that prevents infinite recursion. In the base case, no recursive function calls occur.
Consider the following example code below.
function recursiveFunction(understandRecursion)
{
const recursAnswer = confirm("Do you understand recursion?");
if(recursAnswer === true) // base case or stopping point.
{
return true;
}
recursiveFunction(recursAnswer); // Recursive call.
}
In this example, the recursiveFunction() function will keep calling itself until recursAnswer is true. In the function body, the conditional statement is used to make a base case.
Example Program based on JavaScript Recursion
1. Let’s take a very simple example program based on recursion. In this example, we will print numbers from counting down from 5 to 1. Look at the following script code.
Program code 1:
<html>
<head>
<title>Program to count down numbers to 1</title>
<script>
function countDown(num)
{
// Displaying the number
document.write(num, "<br>");
// Decreasing the number value by 1.
const newNum = num - 1;
// Base case or stopping point.
if (newNum > 0) {
countDown(newNum);
}
}
countDown(5); // calling function.
</script>
</head>
</html>
Output:
5
4
3
2
1
In the above code, we have passed a number as an argument when calling a function. In the function body, we have used a conditional statement to check the passed argument is greater than zero.
This is a base condition. As long as this conditional is true, the recursive function countDown() calls itself. On each iteration, the number value is decreasing by 1 and function countDown() is called until the number is positive.
Look at the following steps to understand recursive calls more clearly.
countDown(5) prints 5 and calls countDown(4) countDown(4) prints 4 and calls countDown(3) countDown(3) prints 3 and calls countDown(2) countDown(2) prints 2 and calls countDown(1) countDown(1) prints 1 and calls countDown(0)
When the number reaches 0, the conditional statement evaluates to false. Since the base condition met, the function is not called anymore.
Program code 2:
<html>
<head>
<title>Program to count down numbers to 0</title>
<script>
function countDown(num)
{
if(num < 0) // base case. Stop at 0.
{
return; // stop function.
} else {
document.write(num, "<br>");
countDown(num - 1); // count down 1.
}
}
countDown(5); // calling function.
</script>
</head>
</html>
Output:
5
4
3
2
1
0
Factorial Program using Recursion in JavaScript
In this section, we will learn how to compute the factorial of a number using recursion method. A factorial of a number, n, is represented by n!. It is the result of multiplying of a numbers from 1 to n.
For example, the factorial of a number 4 is represented by 4!. It is equal to 4 * 3 * 2 * 1, resulting in 24. General steps to compute the factorial of any number n, as follows: (n) * (n – 1) * (n – 2) * (n – 3) * . . . . . * 1.
Let’s write code to compute the factorial of a number using loop.
Program code 3:
<html>
<head>
<title>Program to compute the factorial of a number using loop</title>
<script>
function fact(num)
{
if(num < 0)
return undefined;
let total = 1;
for(let n = num; n > 1; n--)
{
total = total * n;
}
return total;
}
document.write(fact(6));
</script>
</head>
</html>
Output:
720
In this example, we have computed the factorial starting at given num, and decrease num until it has the value of 2, since the factorial of 1 is 1. We already included it in the total variable. The factorial of zero is also 1. The factorial of negative numbers cannot compute.
Recursive Factorial
Now, let us rewrite the fact function using recursion.
Program code 4:
<html>
<head>
<title>Program to compute the factorial of a number using recursion</title>
<script>
function fact(num)
{
if(num === 1 || num === 0) // base case.
{
return 1;
}
return num * fact(num - 1); // recursive call.
}
document.write(fact(6));
</script>
</head>
</html>
Output:
720
Let’s write an algorithm to compute the factorial of number 6. The recursive call to compute the factorial of a number 6 is as:
- fact(6) returns 6 * fact(5)
- fact(5) returns 6 * 5 * fact(4)
- fact(4) returns 6 * 5 * 4 * fact(3)
- fact(3) returns 6 * 5 * 4 * 3 * fact(2)
- fact(2) returns 6 * 5 * 4 * 3 * 2 * fact(1)
- fact(1) returns 6 * 5 * 4 * 3 * 2 * 1.
- fact(1) or fact(0) returns 1. 1! is equal 1 and 0! is also 1.
At beginning, you may seem that recursive functions are more difficult, but they become easier with practice some programs.
Fibonacci Series using Recursion in JavaScript
The Fibonacci series is a list of infinite numbers, each of which is the sum of past two numbers (starting with 1). For example, 1, 1, 2, 3, 5, 8, 13, 21, . . . . . . .
Let’s write a JavaScript program to print 20th of the Fibonacci sequence.
Iterative Solution: Fibonacci Series
Let’s write JavaScript code for Fibonacci series using for loop. This is an iterative solution.
Program code 5:
<html>
<head>
<title>Program to sum the Fibonacci series of a number using for loop</title>
<script>
function getFibo(num)
{
if(num <= 1)
return num;
let sum = 0;
last = 1;
lastlast = 0;
for(let i = 1; i < num; i++)
{
sum = lastlast + last;
lastlast = last;
last = sum;
}
return sum;
}
document.write("Sum of Fibonacci numbers: " +getFibo(10));
</script>
</head>
</html>
Output:
Sum of Fibonacci numbers: 55
Here, we have used for loop to keep the track of last two elements of the Fibonacci series, and its sum yields the Fibonacci number.
Recursive Solution: Fibonacci Series
Let’s write JavaScript code recursively to yield Fibonacci sequence of a number.
Program code 6:
<html>
<head>
<title>Program to sum the Fibonacci series of a number using recursion</title>
<script>
function getFibo(num)
{
if(num <= 1) // base case.
{
return num;
} else {
return getFibo(num - 1) + getFibo(num - 2);
}
}
document.write("Sum of Fibonacci numbers: " +getFibo(10));
</script>
</head>
</html>
Output:
Sum of Fibonacci numbers: 55
Program to Spell each Digit Separately
Let’s now take one more example program based on recursive function in JavaScript. Suppose we have an input number and then have to spell each digit separately.
For example, we have a number 567 as input and we have to display 5, 6, and 7 separately. Let’s write the JavaScript code for it.
Program code 7:
<html>
<head>
<title>Program to spell each digit separately</title>
<script>
function spell_num(number)
{
if(number < 10) // base case.
{
document.write(number, "<br>");
} else {
spell_num(Math.floor(number / 10)); // recursive call.
document.write(number % 10, "<br>");
}
}
spell_num(567);
</script>
</head>
</html>
Output:
5
6
7
In this example, we have declared a function named spell_num() that takes as input a parameter number. Within the function body, the function checks if the number is less than 10.
The base case is when the number passed as input is less than 10. As a result, the function will return number itself rather than calling the recursive function. The number will directly display as output on the web browser. In this case, no recursive call will happen.
If the number is greater than or equal to 10, the function will call recursively, as shown below list and will pass it the quotient of number divided by 10.
Next, the remainder of number divided by 10 will print as output on the browser. Because we want to print numbers in correct order from left to right, we will call recursive function first and then print the remainder.
For number 567, the sequence of call of function spell_num is as follows:
- function spell_num(567) // function called with input 567.
- function spell_num(56) // function called with input 56.
- function spell_num(5) // function called with input 5.
In this tutorial, we have discussed recursion in JavaScript with some example programs. Recursion is a fundamental programming concept that we can use in the place of looping and in the many complex programs.
If you seem recursion confusing, don’t worry. At starting, you can feel it, but with practice recursion becomes easier.
Thanks for reading!!!
Next ⇒ JavaScript Arrow function⇐ Prev Next ⇒