See recursion as a stack
Updated
Each call pushes a frame (locals, return address, current argument). Return pops it. The caller is buried under the callee. Depth of recursion is the stack size. That is the call stack.
What to focus on
An explicit stack of arguments can replace the call stack for recursion without a compiler (DFS, reverse). If you understand LIFO, you understand why the base case runs before the first caller's leftover work.
Worked examples
fact 3
n = 3, fact(n)=n*fact(n-1)- push 3,2,1, then base, then pop 1,2,3 multiplying
Result: frames 3 then 2 then 1
base first out
n = 1, base returns 1- pop the only frame
Result: 1
empty
n = 0 as base, no recursive call- one frame or none depending on code
Result: no nested frame
Try it
Write traceFact(n). n is a positive integer, the argument to factorial. Print frames as they push n, n-1, …, 1 then pop. The multiply after the recursive call runs on the way out. n = 3, fact(n)=n*fact(n-1) → frames 3 then 2 then 1. n = 1, base returns 1 → 1. n = 0 as base, no recursive call → no nested frame.
n is a positive integer. The base case is n = 1. You never pop a missing frame.