Recursion & the Call Stack

Recursion and the call stack describe how a function calls itself without losing its place. Each call creates a stack frame, the newest frame runs first, and a return value travels back to the caller waiting below it. That stored frame is also why deep recursion can crash before the math gets hard.

The physical model is a stack of sticky notes. You write fact(4) on the first note, then it says, "I need fact(3) before I can finish." So you put a new note on top. Only the top note gets your attention. The lower notes are not gone; they are just waiting with unfinished work. In the animation, each sticky note is one stack frame, and a "note waits" label means that frame has unfinished local work.

Why recursion needs the call stack

A recursive function has two jobs. First, it needs a base case: a condition that can return without making another recursive call. Second, it needs a recursive case: a call on a smaller input, followed by whatever work uses that returned answer.

For factorial, the base case is n <= 1, which returns 1. The recursive case for fact(n) asks for fact(n - 1), stores that answer as child, then returns n * child.

That word "stores" matters. When fact(4) calls fact(3), the fact(4) frame does not vanish. It stays on the call stack with its local n = 4 and an unfinished slot, child = ?. When fact(3) eventually returns 6, that value lands in the waiting slot, and only then can fact(4) compute 4 * 6.

This is last-in, first-out control flow. The last call pushed is the first one that can return. The practical lesson is already visible here: every waiting frame costs stack memory.

Recursion & the Call Stack Step by Step

The default run computes fact(4).

1. The program starts at answer = fact(n), with n = 4. The stack is empty.
2. fact(4) is called, so a new frame is pushed. That frame has local state n = 4.
3. The frame checks 4 <= 1. The answer is false, so it cannot return yet.
4. fact(4) pauses at child = fact(3). Its child slot is waiting.
5. fact(3) is pushed on top. Now fact(3) runs, while fact(4) waits below it.
6. fact(3) checks 3 <= 1, gets false, and pauses at child = fact(2).
7. fact(2) is pushed, checks 2 <= 1, gets false, and pauses at child = fact(1).
8. fact(1) is pushed. Its guard 1 <= 1 is true, so the base case returns 1.
9. That 1 is delivered to the caller, fact(2), filling child = 1.
10. fact(2) can now finish: it returns 2 * 1 = 2.
11. That 2 lands in fact(3) as child = 2, so fact(3) returns 3 * 2 = 6.
12. That 6 lands in fact(4) as child = 6, so fact(4) returns 4 * 6 = 24.
13. The root return value becomes answer = 24, and the stack is empty again.

The important visual signal is the direction change. Calls push frames upward; returns move values downward into the caller that was waiting. If you can explain why fact(2) finishes before fact(4), you have the call-stack model.

After the normal run, switch the code variant to missingBase. Remove the base case and watch why recursion must stop: every top frame asks for one more frame, and none of them reach a return.

Time and Space Complexity

Under this lesson's unit-cost model, the normal factorial program does constant work in each frame: one guard, maybe one recursive call, and at most one multiplication on the way back. With n frames, that is O(n) time and O(n) stack space. That stack-space line is the practical bite: if n can be huge, deep recursion can crash before the math is hard, which is when you rewrite it as a loop, use an explicit stack, or change the recursion limit only on purpose.

The missing-base variant is not "slow factorial." It is not factorial at all. It has no stopping rule, so the only thing that halts it is the runtime's recursion limit. Python's default limit is around 1000 frames, not six; this lesson uses a tiny visible cap so you can see the failure before the screen turns into wallpaper.

Edge Cases

• n = 1 hits the base case immediately. One frame is pushed, returns 1, and pops.
• The maximum normal input here is n = 6, not because factorial stops there, but because six frames are the largest stack that fits cleanly on the teaching canvas.
• In the missing-base variant, negative values do not save you. fact_without_base(-2) still calls fact_without_base(-3), then -4, then keeps going.
• A return value always goes to exactly one place: the caller's waiting child slot, or the global answer slot for the root call.

Common Mistakes

• Thinking recursion creates copies of the whole program. It creates a new frame for the same function, with its own local variables.
• Forgetting that callers are suspended. fact(4) cannot multiply until fact(3) has returned.
• Treating the base case as optional. Without it, the stack grows until the runtime stops the program.
• Mixing up return order with call order. Calls go 4, 3, 2, 1; returns come back 1, 2, 6, 24.
• Reusing one shared child variable in your mental model. Each frame has its own child; fact(2).child and fact(4).child are different slots.

A Note on Simplification

This visualization shows a teaching stack frame: function name, argument, local child, and return value. Real Python frames also carry bytecode positions, globals, closure references, exception state, and interpreter bookkeeping. Those details matter to runtime engineers, but they would hide the first idea: recursion works because each call has its own frame, and the top frame is the only one currently running.