Python Recursion Explained

Recursion is when a function calls itself to solve a smaller version of the same problem, until it reaches a case simple enough to answer directly. Every working recursive function needs exactly two parts: a base case that stops the recursion, and a recursive case that calls the function again with input that moves closer to that base case.

A Simple Example: Factorial

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

print(factorial(5))

Output:

120

Tracing this by hand helps it click: factorial(5) calls factorial(4), which calls factorial(3), and so on down to factorial(1), which returns 1 immediately without recursing further. Then each call multiplies its own n by the result it got back, unwinding all the way up to the original call: 5 * 4 * 3 * 2 * 1 = 120.

Why the Base Case Matters

# Missing base case — never stops recursing
def broken_factorial(n):
    return n * broken_factorial(n - 1)

broken_factorial(5)

Output:

RecursionError: maximum recursion depth exceeded

Without a base case, the function keeps calling itself with smaller and smaller values of n forever — Python eventually hits its recursion limit (around 1000 calls deep by default) and raises an error rather than crashing with a stack overflow.

When Recursion Isn't the Best Choice

Recursion reads beautifully for problems that are naturally defined in terms of themselves — factorials, tree traversals, backtracking — but it isn't free. Each call adds a new frame to the call stack, which costs memory and, for Python specifically, is usually slower than an equivalent loop because Python doesn't optimize "tail calls" the way some other languages do. For a problem like plain Fibonacci, naive recursion can also recompute the same values over and over, which is why techniques like memoization exist — see our worked example in optimizing Fibonacci with memoization. As a rule of thumb: if an iterative loop solves the problem just as clearly, prefer the loop; reach for recursion when the problem itself is naturally recursive, like trees, graphs, or divide-and-conquer algorithms.