The Call Stack

When a subroutine is called, the CPU stores execution context information on the call stack — a LIFO (Last In, First Out) data structure held in memory. Each entry on the call stack is called a stack frame.

What a Stack Frame Contains

Stack Frame Lifecycle

PUSH — When a subroutine is called, a new stack frame is pushed onto the top of the call stack.

POP — When the subroutine returns, its stack frame is popped off, restoring the previous frame and resuming from the stored return address.

Recursion

Recursion is a programming technique where a subroutine calls itself. Each call creates a new stack frame, building up the call stack until the base case is reached.

Requirements for a Valid Recursive Algorithm

• Base case — a condition that stops the recursion (returns without making a recursive call)
• Recursive case — the function calls itself with a smaller/simpler version of the problem, progressing toward the base case

Example: Factorial (n!)

FUNCTION factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1          // Base case: 0! = 1
    ELSE
        RETURN n * factorial(n - 1)   // Recursive case
    ENDIF
ENDFUNCTION

Trace of factorial(3):

factorial(3) → 3 × factorial(2)
factorial(2) → 2 × factorial(1)
factorial(1) → 1 × factorial(0)
factorial(0) → 1              // base case

Unwinding:
factorial(1) → 1 × 1 = 1
factorial(2) → 2 × 1 = 2
factorial(3) → 3 × 2 = 6

Example: Fibonacci

FUNCTION fib(n : INTEGER) RETURNS INTEGER
    IF n ≤ 1 THEN
        RETURN n
    ELSE
        RETURN fib(n-1) + fib(n-2)
    ENDIF
ENDFUNCTION

Stack Overflow

Each recursive call adds a new stack frame. If the base case is never reached (or is reached too late), the call stack runs out of memory — this is called a stack overflow and causes a runtime error.

Causes of stack overflow from recursion:

• Missing or incorrect base case
• Recursive case that does not progress toward the base case
• Extremely deep recursion (very large n)

Recursion vs. Iteration