A recursive function is a function that calls itself. It sounds strange the first time you see it, but it is just a way to solve a big problem by solving a smaller copy of the same problem — and then a smaller one, and a smaller one — until the problem is so tiny the answer is obvious. We will trace factorial(4) and watch two things at once: the call stack and the recursion tree.
Step through the animation on the right. Watch frames get pushed onto the call stack as each call goes deeper, the base case turn green when it stops the descent, and then the results unwind back up the stack until factorial(4) becomes 24.
The idea
Every recursive function has two parts:
- A base case — the simplest input, where you return an answer directly without calling yourself again. This is what stops the recursion. For factorial it is
n == 1, which returns1. - A recursive case — where you call yourself with a smaller input and build your answer from the result. For factorial it is
n * factorial(n - 1).
Each call waits, paused, until the call it made comes back with an answer. The computer remembers all these paused calls on the call stack — one frame per call. When a call returns, its frame is popped off and the value flows back to whoever was waiting.
Walk through it
Press Play on the right, or step with Next / Back. The animation runs in two halves:
- Going down (the calls). Each call pushes a new frame onto the call stack and adds a node to the recursion tree. The stack grows until factorial(1) sits at the bottom — four frames deep.
- Coming back up (the returns). factorial(1) hits the base case and returns
1. Its frame pops. Now factorial(2) can finish:2 * 1 = 2. Then factorial(3):3 * 2 = 6. Then factorial(4):4 * 6 = 24. Each return pops a frame and feeds its value to the call above it.
The deepest call is solved first, and the original call is solved last. That "down, then back up" shape is the heart of every recursive trace.
The code, line by line
def factorial(n):
if n == 1: # base case
return 1
return n * factorial(n - 1)- Line 1 defines the function. Each call gets its own copy of
n— that is why factorial(4) and factorial(2) do not clobber each other's value. - Lines 2–3 are the base case. When
nreaches 1, we return1straight away. Without this line the function would call itself forever and crash with a "maximum recursion depth" error. - Line 4 is the recursive case. It calls
factorial(n - 1)— a smaller problem — and multiplies the result byn. This line both makes the call (going down) and does the multiply (coming back up).
A word on backtracking
Backtracking is recursion with an undo step. You make a choice, recurse to explore it, and if that path fails you return and undo the choice before trying the next one — exactly like popping a frame off the call stack. Problems like solving a maze, placing N queens on a chessboard, or generating every permutation are all "try a choice, recurse, then back up and try the next." The call stack you see in this animation is what makes that automatic undo possible.
Complexity
| Case | Time | Notes |
|---|---|---|
| Time | O(n) (moderate) | one call per value from n down to 1 |
| Space | O(n) (moderate) | n frames stacked at the deepest point |
O(n) (moderate)factorial(n) makes n calls in total, so the time is O(n). The space is also O(n) — and this is the surprise. Even though we never make a copy of an array, the call stack holds up to n frames at the deepest point. Every recursive call costs memory until it returns. That is why very deep recursion can overflow the stack.
When to use / pitfalls
Recursion shines when a problem is naturally self-similar — trees, nested structures, divide-and-conquer (merge sort, quick sort), and backtracking. In an interview, always state your base case first: it is the part that makes the recursion stop, and forgetting it is the number one recursion bug. If the input can be very large and deep, mention that an iterative version with an explicit stack avoids the stack-overflow risk.
Two classic mistakes: (1) no base case, or a base case the recursion never reaches — the stack grows until the program crashes. (2) Recursing on input that is not smaller each time, so you never approach the base case. Every recursive call must move toward the base case.
Practice
In the trace of factorial(4), which call returns its value FIRST — and which returns LAST?
1. What is the job of the base case?
2. In what order are the results computed in factorial(4)?
3. Why is the space complexity of factorial(n) O(n)?
4. What is backtracking?