JavaScript Recursion

In JavaScript, recursion refers to a technique where a function calls itself.

The syntax of a recursive function is:

function recurse() {

    // body of function

    // call function recursively
    recurse();

    // body of function
}

recurse();

In the above example, recurse() calls itself through its body.

Base Case

A base case is a condition that determines when the recursion should stop.

Every recursive function must have a base case. Otherwise, the function is called infinitely.

We use conditional statements such as if...else or the ternary operator to create base cases.

The syntax of a recursive function with a base condition looks like this:

function recurse() {

    // base case
    if(condition) {
        recurse();
    }
    else {
        // stop calling recurse()
    }
}

recurse();

Flowchart of Recursive Function

Example 1: Countdown Till 1

// Program to count down numbers to 1

// recursive function
function countDown(num) {

    // display num
    console.log(num);

    // decrease num
    // then, assign new value to newNum
    const newNum = num - 1;

    // base case
    if (newNum > 0) {

        // call countDown with newNum
        countDown(newNum);
    }
}

countDown(3);

Output

3
2
1

In the above program, we have called the countDown() function recursively.

The base case is newNum > 0, which means countDown() must keep calling itself as long as the value of newNum is greater than 0.

Here is how the above program works:

Example 2: Find Factorial

// Program to find the factorial of a number

// recursive function
function factorial(num) {

    // base case
    // recurse only if num is greater than 0
    if (num > 1) {
        return num * factorial(num - 1);
    }
    else {
        return 1;
    }
}

let x = 3;

// store result of factorial() in variable
let y = factorial(x);

console.log(`The factorial of ${x} is ${y}`);

Output

The factorial of 3 is 6

Here, the factorial() function calls itself recursively as long as the num variable is greater than 1.

We can divide the overall recursion process into two halves.

The first half includes:

This is how the first half of the recursive process works:

1. First, factorial(3) returns 3 * factorial(2) and waits for factorial(2) to compute.
2. Then, factorial(2) returns 2 * factorial(1) and waits for factorial(1) to compute.
3. Finally, factorial(1) doesn't pass the base case, so it directly returns 1.

After that, the second half takes place in reverse:

Here, after factorial(1) returns 1, factorial(2) returns 2 * 1.

Finally, factorial(3) returns 3 * 2, which is stored in the result variable.