Recursion Fundamentals

The two questions

Every recursive function answers two questions:

1. What is the smallest input I can answer immediately? That is the base case.
2. How do I reduce a larger input to a smaller one? That is the recursive step.

Miss the base case and the function never stops. Miss the shrinking and it never reaches the base case. Both produce a stack overflow.

A worked example

Factorial is the standard introduction because both parts are obvious:

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

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24

Notice that nothing multiplies until the base case returns. Each call waits on the call stack for the one below it, which is why the space cost is $O(n)$ even though a single number comes back.

The leap of faith

The hardest part of recursion is psychological. You do not need to trace every level in your head. Instead, assume the recursive call already works correctly for a smaller input, and ask only whether you combine its result properly.

This is the same reasoning as mathematical induction, and getting comfortable with it is what makes trees and graphs feel manageable later.

Try it

Write a recursive function that reverses a string.

Recursion versus iteration

Anything recursive can be written iteratively and vice versa. Choose based on which expresses the problem more clearly.

Here is the same sum written both ways:

def sum_recursive(nums, i=0):
    if i == len(nums):
        return 0
    return nums[i] + sum_recursive(nums, i + 1)


def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

Both are $O(n)$ time, but the recursive version uses $O(n)$ stack space while the loop uses $O(1)$.

When recursion hurts

Naive Fibonacci recomputes the same values an exponential number of times:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

The fix is memoization: cache each result the first time you compute it.

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Now every value is computed once, bringing it down to $O(n)$ time and $O(n)$ space. This idea is the entire foundation of dynamic programming, which you will meet later in the course.

Common mistakes

1. No base case, or a base case the recursion can skip past (for example checking n == 0 while decrementing by 2).
2. Not shrinking the input — calling f(n) instead of f(n - 1).
3. Mutable default arguments. In Python, def f(x, seen=[]) reuses the same list across calls. Use None and create it inside, as shown above.
4. Ignoring stack depth. Python's default limit is around 1,000 frames.

Summary

Write the base case first, make sure every call moves toward it, and trust that the recursive call handles the smaller problem. When subproblems repeat, add memoization to collapse exponential work into linear.