Recursion

Overview

Recursion is when a function solves a problem by calling itself on a smaller version of that problem. Every recursive solution needs a base case that stops the recursion and a recursive case that moves toward it. It is a natural fit for problems with self-similar structure, like trees, factorials, and divide-and-conquer algorithms.

Syntax / Usage

Define the base case first so the function can stop, then reduce the input in the recursive call. Watch the call depth, since each pending call uses stack space.

def factorial(n):              # O(n) time, O(n) call-stack space
    if n <= 1:                 # base case
        return 1
    return n * factorial(n - 1)  # recursive case moves toward base

def sum_list(items):
    if not items:              # base case: empty list
        return 0
    return items[0] + sum_list(items[1:])

Examples

Factorial multiplies down to the base case:

print(factorial(5))  # 120  (5 * 4 * 3 * 2 * 1)

Recursion mirrors nested structure, such as summing a nested list:

def deep_sum(data):
    total = 0
    for item in data:
        total += deep_sum(item) if isinstance(item, list) else item
    return total

print(deep_sum([1, [2, 3], [4, [5]]]))  # 15

Common Mistakes

• Missing or unreachable base case, causing a RecursionError from infinite calls.
• Not shrinking the input, so the recursive call never approaches the base case.
• Ignoring stack depth limits; deep recursion can overflow (Python defaults to ~1000).
• Recomputing the same subproblems repeatedly instead of caching results.
• Choosing recursion where a simple loop is clearer and uses O(1) space.

See Also

algorithms-sorting algorithms-dynamic-programming algorithms-big-o-notation