Recursion & Call Stack Frames

1. Self-Referential Functions

Recursion is a problem-solving technique where a function solves a smaller sub-instance of the same problem by calling itself.

2. Anatomy of a Recursive Function

Every recursive function MUST have two parts:

1. Base Case: A termination condition that stops recursion and returns a concrete result directly.
2. Recursive Step: Reduces the problem size and calls the function again toward the base case.

function factorial(n) {
  // Base Case
  if (n <= 1) return 1;

  // Recursive Step
  return n * factorial(n - 1);
}

console.log(factorial(4)); // Output: 24 (4 * 3 * 2 * 1)

3. Visualizing Call Stack Frames

Each recursive call allocates a new stack frame in memory storing local variables:

[ factorial(1) -> returns 1 ]  ◄── Base Case Reached (Stack Unwinds)
[ factorial(2) -> 2 * 1     ]
[ factorial(3) -> 3 * 2     ]
[ factorial(4) -> 4 * 6     ]  ◄── Initial Invocation

4. Space Complexity of Recursion

Recursive functions consume O(D) auxiliary space on the call stack, where D is the maximum recursion depth.

5. Common Mistakes

• Missing or Incorrect Base Case: Calling recursion without a base case leads to infinite execution until the runtime throws RangeError: Maximum call stack size exceeded (Stack Overflow!).
• Redundant Recalculations: Naive recursive Fibonacci (fib(n) = fib(n-1) + fib(n-2)) runs in horrific O(2^N) exponential time due to repeating identical subproblems. Use memoization or dynamic programming to reduce to O(N)!

6. Next Steps

Mastering recursion is required for trees and backtracking. Next, let's explore Backtracking Patterns!