JS Recursive Functions

JavaScript Recursive Functions

In some cases, you might want to call a function from inside that exact same function. This concept is known as Recursion.

A recursive function is simply a function that calls itself. While it can be a beautiful and elegant solution to rather complex programming problems, there are some important rules to keep in mind.

The Danger of Infinite Recursion

When a function calls itself, it creates a loop. But what happens if we never tell that loop to stop?

What do you think this code will do?

function getRecursive(nr) {
    console.log(nr);
    getRecursive(--nr); // The function calls itself!
}

getRecursive(3);

Why is it not stopping? Because we are not telling the function when it should stop calling itself.

Adding a Stop Condition (The Base Case)

To fix the infinite loop, every recursive function must have a stop condition (often called a Base Case by programmers).

Look at our improved version:

function getRecursive(nr) {
    console.log(nr);
    // The Stop Condition (Base Case)
    if (nr > 0) {
        getRecursive(--nr);
    }
}

getRecursive(3);

This function is going to call itself until the value of the parameter is no longer bigger than 0. Once nr hits 0, the if condition becomes false, the function stops calling itself, and the recursion safely ends.

Understanding the Call Stack

What actually happens behind the scenes when we call a function recursively is that JavaScript goes one function "deeper" every time.

Because the newest function call must finish before the previous one can continue, the very first function call is actually the last one to finish. For our getRecursive(3) function, the order of execution looks like this:

• 🟢 getRecursive(3) starts
  • 🟢 getRecursive(2) starts
    • 🟢 getRecursive(1) starts
      • 🟢 getRecursive(0) starts
      • 🔴 done with getRecursive(0) execution
    • 🔴 done with getRecursive(1) execution
  • 🔴 done with getRecursive(2) execution
• 🔴 done with getRecursive(3) execution

Visualizing the Unwinding Process

The next recursive function will perfectly demonstrate how the functions stack up and then "unwind" in reverse order:

function logRecursive(nr) {
    console.log("Started function:", nr);
    if (nr > 0) {
        logRecursive(nr - 1);
    } else {
        console.log("Done with recursion");
    }
    console.log("Ended function:", nr);
}

logRecursive(3);

Notice how the "Ended" logs happen in completely reverse order? That is because logRecursive(3) cannot log its "Ended" message until logRecursive(2) has completely finished its job!

When to Use Recursion

Recursive functions can be incredibly powerful in specific contexts.

• Complex Iteration: When you feel the need to call the same function over and over again in a loop to dig deeper into data, you should consider recursion.
• Searching structures: Recursion is widely used for searching through complex nested data structures (like folder directories on a computer, or family trees). Instead of looping over everything inside a single massive function, you can split up the work and call the function repeatedly from the inside.
• Math problems: Things like calculating factorials or the Fibonacci sequence are perfectly suited for recursion.

⚠️ Performance Considerations

However, it must be kept in mind that, in general, the performance of recursion is slightly worse than the performance of regular iteration using a loop.

Every time a recursive function calls itself, it takes up a little bit of memory on the "call stack". If your recursion goes thousands of layers deep, it could cause a bottleneck situation that slows down your application or crashes the browser. In those cases, you might want to consider using a standard while or for loop instead.