Stack Overflow errors occur when the call stack memory threshold is breached. We analyze recursion execution mechanics and show how to fix stack overflow using concrete recursive and iterative code traces.

The Problematic Code: Factorial Without Base Case

def factorial_infinite(n):
    return n * factorial_infinite(n - 1) # Will cause Stack Overflow

The Fixed Code: Factorial With Base Case

def factorial(n):
    if n <= 1: # Base Case
        return 1
    return n * factorial(n - 1)

Step-by-Step Call Stack Trace

Let's trace factorial(3) step-by-step to see how the system's memory behaves:

Call Stack Memory Frames:
  1. factorial(3) is called. A stack frame is pushed: n = 3. It waits for the result of factorial(2).
  2. factorial(2) is called. A stack frame is pushed: n = 2. It waits for the result of factorial(1).
  3. factorial(1) is called. A stack frame is pushed: n = 1. This matches our **Base Case**, returning 1 immediately.
  4. Unwinding (Popping) Phase:
    • The frame for factorial(1) returns 1 and is popped.
    • The frame for factorial(2) receives 1, calculates 2 * 1 = 2, and is popped.
    • The frame for factorial(3) receives 2, calculates 3 * 2 = 6, and is popped, returning the final answer 6.

Without the base case, the stack continues pushing frames (n = 0, -1, -2, ...) infinitely until it hits the compiler/interpreter limit and throws a **StackOverflowError**.