Base CS from zero

Recursion preview

Crux A recursive function calls itself. Each call is just another frame on the stack. The base case stops the descent. Without a base case, the stack overflows.

◷ 22 min

You have traced call stacks where main calls outer calls inner. Each call pushes a new frame. But nothing in the rules says a function cannot call itself. What happens to the stack then?

The answer is: exactly the same thing. A function calling itself is just another CALL instruction pointing to the same function address. A new frame is pushed, with its own copy of the parameters and locals. The function is not “re-entered” — a second, independent instance of the frame is created. This is recursion.

The critical constraint: something must eventually stop the descent, or the stack grows until it overflows. That stopping condition is the base case.

Goal

After this lesson you can explain what a recursive function is (a function that calls itself), describe each recursive call as a new independent frame on the stack, identify the base case and the recursive case in a function, and explain what causes a stack overflow in a recursive program.

The idea

Recursion has exactly two parts:

The base case — the condition under which the function does not call itself and instead returns a direct value. The base case is the bottom of the descent. Without it, recursion never stops.
The recursive case — the condition under which the function calls itself with a “smaller” input, working toward the base case. “Smaller” means closer to the base case, not necessarily numerically smaller.

Each recursive call creates a new frame on the stack. The call chain grows downward (more frames) until the base case is hit. Then the chain unwinds upward (frames pop) as each call returns its result to the caller above it.

The function to trace: countdown(n) prints (conceptually) n, n-1, …, 1, 0, and then one more call that hits the base case. The base case is n < 0 (stop below zero — it fires when n reaches -1). The recursive case calls countdown(n - 1). Traced with countdown(3).

Why countdown rather than factorial? Because the stack trace is easier to hold in mind for three levels: the trace shows frames accumulating to depth 4 (n=3,2,1,0) and then popping. The same pattern applies to factorial, merge sort, tree traversal — all recursive algorithms rest on the same stack mechanism.

The code


      1
      function countdown(n: number): void {
    

      2
      if (n < 0) return;          // base case: stop below zero
    

      3
      // (in a real program we would print n here)
    

      4
      countdown(n - 1);           // recursive call: n shrinks by 1
    

      5
      }

L1 n is a parameter: each call gets its own n in its own frame
L2 base case: when n < 0, return without calling again — stops the descent
L4 recursive case: CALL countdown with n-1; pushes a new frame for the next level

countdown(n): the base case n < 0 stops the recursion. Each call pushes one new frame. countdown(3) creates 5 frames total (n=3,2,1,0,-1 at n<0 base case).

Step-by-step trace

Trace countdown(3). Each cell is one frame. Frames accumulate as n decreases, then unwind as each call returns.


      1
      function countdown(n: number): void {
    

      2
        if (n < 0) return;
    

      3
        countdown(n - 1);
    

      4
      }

Edge cases

What if there is no base case? Remove the if (n < 0) return; line. Now countdown(-1) calls countdown(-2), which calls countdown(-3), and so on forever. Each call pushes a new frame. The stack region (typically 1–8 MB) fills up. When the stack pointer would move past the end of the reserved region, the OS terminates the program with a “stack overflow” error. This is not a slow bug — it crashes the program within milliseconds because each call takes only nanoseconds and millions can happen before the stack exhausts. The base case is not optional in recursive functions.

Practice 0 / 5

countdown(3) is called. Including the base case call (n=-1), how many frames are pushed onto the stack in total?

At what value of n does the base case fire in countdown?

countdown(3) calls countdown(2), which calls countdown(1), ..., down to the base case. The maximum number of frames on the stack at once is 5 (for n=3,2,1,0,-1). If countdown(10) were called, what is the maximum number of frames on the stack at once?

A recursive function has no base case. What happens when it is called? Type 1 for 'stack overflow', 0 for 'returns normally'.

function factorial(n: number): number { if (n === 0) return 1; return n * factorial(n - 1); } — What is the base case value of n?

Check yourself

Quiz

What makes recursion safe (i.e., what prevents the stack from overflowing)?

Recap

A recursive function calls itself. Each call is just a CALL to the same function address, which pushes a new, independent frame with its own copy of the parameters. Recursive calls nest on the stack exactly like any other call chain. The descent continues until the base case — the condition that returns a value without making another call — is reached. Once the base case fires, the stack unwinds: frames are popped one by one as each call returns to its caller. Without a base case, frames accumulate without bound until the stack region is exhausted and the program crashes with a stack overflow. Every safe recursive function must have a base case that is reachable for all valid inputs.

Continue the climb ↑Functions and the call stack: multiple-choice review