Recursion & Call Stack Frames

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

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!