Calls stack up
Line 6 calls fact(4). Python makes a call frame for it: scratch space that holds this call’s own n, here 4. fact is recursive: to find its answer, it calls itself on a smaller problem.
Is 4 <= 1? No, so line 4 runs: 4 * fact(3). fact(4) cannot finish until it knows fact(3). It waits, and a new frame for fact(3) is stacked on top, with its own n = 3.
fact(3) does the same: it waits on 3 * fact(2), and a frame for fact(2) goes on top. Each waiting call keeps its own n. This pile of frames is called the call stack.
fact(2) asks for fact(1). Four frames are stacked now, one for each call still running. Every call moved closer to the end, because n gets 1 smaller each time.
Base case
In fact(1), n <= 1 is true, so line 3 returns 1 straight away, with no new call. This is the base case: a problem small enough to answer directly. Without it, the calls would never stop.
Unwinding
fact(1) returns 1 to the call below it, and its frame is removed. fact(2) carries on from where it paused and finishes line 4: 2 * 1 = 2.
fact(2) returns 2 and its frame goes. fact(3) carries on: 3 * 2 = 6. The last call to start is the first to finish, like taking plates off the top of a pile.
fact(3) returns 6. Now fact(4), the first call, can finish: 4 * 6 = 24. That is 4 * 3 * 2 * 1, multiplied together on the way back down.
fact(4) returns 24 to line 6, its frame is removed, and print shows 24. The stack is empty again: every call that started has finished.
Limits and loops
Every waiting call holds a frame, so Python sets a limit: sys.getrecursionlimit() gives 1000 by default. Go deeper, or leave out the base case, and Python stops with a RecursionError instead of stacking frames forever.
The same answer can come from a loop that multiplies 2, 3 and 4 into one variable. It runs in a single frame, so it never hits the limit. Recursion reads best when a problem holds smaller copies of itself.
Repeated work
fib(n) adds fib(n - 1) and fib(n - 2), so each call calls itself twice. fib(5) then makes 15 calls: fib(2) is worked out 3 times, fib(1) 5 times. Saving each answer to reuse is dynamic programming.
Try it in the Python prompt
;; step 1/12 · line 6: print(fact(4)) >>> def fact(n): ... if n <= 1: ... return 1 ... return n * fact(n - 1) ... >>> fact(4) 24
The drawing shows one block for each call of fact that is still running, stacked in the order the calls started. In CPython every call gets its own frame object; when the call returns, the frame is released. The depth shown counts only fact’s frames. The code that called fact(4) runs in a frame too, so Python’s own count is a little higher, which is why fact(999) still works in a fresh python3 -c run and fact(1000) does not.