Recursion: a function that calls itself

Recursion: solve it in terms of a smaller self

Some data has no fixed depth. A folder holds files and more folders. A JSON payload nests objects inside arrays inside objects. A comment thread has replies to replies to replies. You cannot write a for loop with the "right" number of levels, because you do not know the depth ahead of time. Recursion handles this: a function solves a problem by calling itself on a smaller piece, until the pieces are small enough to answer outright.

The mental model

Every recursive function needs exactly two parts:

1. A base case: the smallest input you can answer directly, with no further call. This is what stops the chain.
2. A recursive case: reduce the problem toward the base case, call yourself on the smaller input, and combine that result.

The trick is to trust the recursive call. When you write factorial(n - 1), assume it already returns the correct answer for n - 1, then build the answer for n on top of it. You do not trace the whole thing in your head. You define one honest step plus a stopping point, and the machine does the rest.

def factorial(n):
    if n <= 1:                     # base case: 0 and 1 both give 1
        return 1
    return n * factorial(n - 1)    # recursive case

print(factorial(5))   # 120

factorial(5) becomes 5 * factorial(4), then 5 * 4 * factorial(3), and so on down to factorial(1), which returns 1 directly. Then the paused multiplications finish on the way back up: 5 * 4 * 3 * 2 * 1 = 120.

The call stack

Here is factorial(3) traced frame by frame, the same shape as factorial(5) but shorter: each call pushes a frame down to the base case, then the frames pop and the paused multiplications finish on the way back up.

Call stack — factorial(3)

Step 1 / 5

factorial(3)

3 > 1, recurse on 2

Each call pauses and waits for the call it made. Python stacks these paused frames until the base case returns, then unwinds them one at a time, applying each pending multiply. If the base case is never reached, the stack keeps growing and Python raises RecursionError after roughly 1000 nested calls (the default sys.getrecursionlimit()).

Pitfalls

A base case that skips 0. Writing if n == 1 looks fine until you call factorial(0): it does not match, so you compute 0 * factorial(-1) * factorial(-2) ... forever, straight to RecursionError. Use if n <= 1 so both 0 and 1 hit the base case and return 1 directly. That is exactly why the exercise pins factorial(0) to 1.

Not shrinking toward the base. The recursive call must move closer to the base case every time. A factorial(n) that calls factorial(n) never ends.

For the nested-sum exercise, your base case is a plain number and your recursive case is a list. Check which one you have with isinstance(x, list): if it is a list, recurse into it and add the pieces; otherwise it is a number, so add it directly. That single isinstance check is what lets one function reach any depth without knowing the shape in advance.

Interview nuance: Python has no tail-call optimization, so a recursive solution uses O(n) call-stack space, one frame per pending call, while an equivalent loop uses O(1). Interviewers probe this: recursion over a length-n structure can overflow the stack where a loop would not, which is why tree and graph problems often call out the depth explicitly. Recursion buys clarity on nested data. It does not buy free memory.