Recursion and Stack in JavaScript

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. Each recursive call is stored in the call stack, which helps track execution.

What is Recursion?

A function is recursive if it calls itself within its own body.

Example: Counting Down

function countdown(n) {
    if (n <= 0) {
        console.log("Done!");
        return;
    }
    console.log(n);
    countdown(n - 1); // Recursive call
}

countdown(5);

🔹 Output:

5
4
3
2
1
Done!

Understanding the Call Stack

JavaScript uses a call stack to track function calls. Each function call is pushed onto the stack and removed when it returns.

Example: Factorial Calculation

function factorial(n) {
    if (n === 1) return 1;
    return n * factorial(n - 1);
}

console.log(factorial(5)); 
// Output: 120

Call Stack Flow for factorial(5)

factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1)
factorial(1) returns 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
factorial(5) returns 5 * 24 = 120

The last function in the stack executes first (LIFO - Last In, First Out).

Base Case and Infinite Recursion

A base case is needed to stop recursion, or the function will keep calling itself indefinitely, causing a stack overflow.

🚨 Example of Infinite Recursion (❌ BAD)

function infiniteRecursion() {
    console.log("Calling...");
    infiniteRecursion(); // No base case!
}

infiniteRecursion(); // ❌ Causes a stack overflow

✅ Always define a base case to stop recursion.

Recursion vs Iteration

Example: Finding the Sum of Numbers

Recursive Approach

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

console.log(sum(5)); // Output: 15

Iterative Approach

function sumIterative(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

console.log(sumIterative(5)); // Output: 15

When to Use Recursion?

Problems that require breaking into smaller subproblems (e.g., trees, graphs, backtracking).
When iteration would make the code more complex.

Common Recursive Problems

Fibonacci Sequence

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // Output: 8

Optimization: The recursive Fibonacci approach has O(2ⁿ) complexity, so memoization (caching results) can improve performance.

Tail Recursion (Optimization)

Some languages optimize recursive functions by using tail recursion (where the recursive call is the last operation), but JavaScript does not optimize it well.

Tail Recursive Sum

function sumTail(n, acc = 0) {
    if (n === 0) return acc;
    return sumTail(n - 1, acc + n);
}

console.log(sumTail(5)); // Output: 15

🎯 Summary

✔ Recursion is when a function calls itself to solve a smaller problem.
✔ Base cases are essential to stop infinite recursion.
✔ Call Stack follows LIFO (Last In, First Out).
✔ Recursion vs Iteration: Use recursion for problems like trees, graphs, and backtracking.
✔ Optimization: Use memoization or tail recursion to improve performance.

🚀 Recursion is a powerful concept, but be cautious about stack overflow! Let me know if you need more examples. 😊

Souy Soeng

Recursion and Stack in JavaScript