Memory Management in Recursion

Every time a function is called in JavaScript, the engine allocates memory to store its state. In recursion, this process happens repeatedly.

The Call Stack

The Call Stack is a LIFO (Last In, First Out) data structure that keeps track of function execution.

How it works with Recursion:

1. Push: Each recursive call creates a new active frame and pushes it onto the top of the stack.
2. State Storage: Each frame stores:
   • Local variables
   • The return address (where to go back after the function ends)
   • Parameters passed to the function
3. Pop: When the base case is reached, the top frame is completed and "popped" off the stack, and control returns to the frame below it.

Bidirectional Execution

Recursion moves in two distinct phases:

1. Forward Phase (Winding): The stack grows as calls are made. Logic placed before the recursive call executes now.
2. Backward Phase (Unwinding): The stack shrinks as functions return. Logic placed after the recursive call executes now.

function bidirectional(n) {
    if (n <= 0) return;
    
    console.log("Forward:", n);  // Executed during Winding
    bidirectional(n - 1);
    console.log("Backward:", n); // Executed during Unwinding
}

Stack Overflow

A Stack Overflow Error occurs when the call stack exceeds its size limit. This most commonly happens because:

• Missing Base Case: The function never stops calling itself.
• **Incorrect Base Case:**The condition is never satisfied.
• Too Deep Recursion: The logic requires more calls than the stack can hold (e.g., recursing 100,000 times).

[!WARNING] Infinite recursion will freeze the browser or environment before eventually throwing RangeError: Maximum call stack size exceeded.

Static and Global Variables

In recursion, you might need variables that survive across calls.

• Global Variables: Defined outside the function. Shared by all calls but can be dangerous due to side effects.
• Closures/Internal State: Passing an object or using a closure to maintain state without global pollution.

let globalCounter = 0; // survives across all calls
 
function countCalls(n) {
    if (n <= 0) return;
    globalCounter++;
    countCalls(n - 1);
}

Conclusion

Understanding the call stack is the key to mastering recursion. It explains why recursion uses more memory than loops ($O(n)$ space vs $O(1)$ space) and why the order of code determines when logic executes.