Recursion and the call stack

The base case stopped it: lists of length 0 or 1 returned immediately without any further calls.

The line was if len(nums) <= 1: return nums, and it was the first thing in the function for a reason.

Every self-calling function needs a case like that, an input so small the answer is immediate. Without one there is nothing to stop the descent.

The other half of the guarantee is that each call must move toward that case. merge_sort sliced the list in half, so the sizes strictly shrank and the base case was always reachable.

This unit makes recursion a tool you control rather than one you trust.

Recursion and the call stack

Half of what remains in this course is recursion wearing different clothes: backtracking, DFS, dynamic programming, plus the merge sort you already met.

Recursion exists because so much real data is self-similar. A directory contains directories, a JSON object contains objects, and the left half of a list is itself a list.

Code that processes such a structure most naturally calls itself on the smaller copies inside it, since a plain loop has no clean way to descend and then come back.

Recursion is a function calling itself on a smaller version of its own problem. Every correct recursive function has exactly two parts.

1. A base case, an input so small you return the answer directly, with no self-call.
2. A recursive case, where you do a little work and then call yourself on something strictly closer to the base case.

The classic example is factorial(n), which is n × (n−1) × ... × 1.

• Base case: factorial(1) is 1.
• Recursive case: factorial(n) is n * factorial(n - 1).

When a function calls itself, Python pauses the caller and remembers where it was. Those paused calls pile up on the call stack, the same last-in-first-out structure from Data Structures, and returns pop them off in reverse order.

That stack is not free. Each paused call holds its own local variables, which is why recursion depth is a real resource with a real limit.

Watching the stack grow and unwind

The indentation mirrors the call stack, since deeper calls print further right.

def factorial(n):
    print("  " * (3 - n) + f"factorial({n}) called")
    if n <= 1:
        print("  " * (3 - n) + "base case: returning 1")
        return 1
    result = n * factorial(n - 1)
    print("  " * (3 - n) + f"factorial({n}) returning {result}")
    return result

print("answer:", factorial(3))

Output

factorial(3) called
  factorial(2) called
    factorial(1) called
    base case: returning 1
  factorial(2) returning 2
factorial(3) returning 6
answer: 6

The three "called" lines print before any "returning" line, which is the stack growing. All three calls are alive at once, paused partway through their own execution.

The base case returns first, and only then can anything else finish. factorial(2) had been waiting on factorial(1) since before that call even printed.

The returns then unwind in reverse order, which is the defining behavior of a stack. Each frame resumes exactly where it paused, multiplies by its own n, and hands the result up.

result is a separate local variable in each frame. factorial(3) and factorial(2) both have one, holding 6 and 2, and they never interfere.

The maximum depth here was 3, and each of those frames is memory the program cannot reclaim until the recursion bottoms out.

total, without any loop

The total of an empty list is 0, and the total of anything else is the first element plus the total of the rest.

def total(nums):
    if not nums:
        return 0
    return nums[0] + total(nums[1:])

print(total([2, 4, 6]))
print(total([]))

Output

12
0

if not nums: return 0 is the base case, and it must come first. Reversing the two lines would index nums[0] on an empty list and raise IndexError.

Choosing 0 rather than something else is not arbitrary. It is the identity for addition, so adding it changes nothing, which is what makes the empty case fit the same formula as every other case.

nums[1:] is the list without its first element, a strictly smaller problem, and that shrinking is what guarantees the base case is reached.

Tracing it out: total([2,4,6]) is 2 + total([4,6]), which is 2 + 4 + total([6]), which is 2 + 4 + 6 + total([]) = 12.

The honest caveat is cost. Each slice copies the rest of the list, so this is O(n²) time and O(n) stack depth, which makes the loop version better in practice. The recursion is here for the shape, not the speed.

Calls pile up until Python raises RecursionError: maximum recursion depth exceeded.

It does not hang forever, and it does not crash the machine. Python counts stack frames and refuses to go past a limit of about 1,000 by default.

Every unfinished call occupies a frame with its own locals, so with no base case the count only ever grows. factorial(3) would call factorial(2), then factorial(1), factorial(0), factorial(-1), and onward through the negatives.

The limit exists to turn a machine-level stack overflow into a catchable Python exception, which is a friendlier failure than a hard crash.

When you see that error, ask two questions in order. Is the base case missing or unreachable, and does the recursive case actually shrink the problem? A base case of n == 0 with input −1 is present but never hit, which fails the same way.