Recursion Fundamentals

Recursion is a technique where a function solves a problem by calling itself on a smaller or simpler version of the same problem, until it reaches a case simple enough to answer directly without any further calls. It matters because many real-world problems — walking a file system, searching a tree, parsing nested data, exploring every combination of a set — have a naturally recursive structure, and expressing the solution recursively is often shorter and clearer than the iterative equivalent. Recursion is also the foundation for backtracking, divide-and-conquer algorithms, and tree and graph traversals, all of which build directly on the ideas in this lesson.

Overview: How Recursion Works

Every recursive function needs two parts: a base case, a condition simple enough to answer without recursing further, and a recursive case, where the function calls itself with an input strictly closer to the base case. If either part is missing or wrong, the function either never recurses (and can’t solve the general problem) or never stops recursing (and eventually crashes).

Consider a small concrete scenario: counting down from a number to zero. You can describe this recursively as “print the number, then count down from one less than it” — and the counting stops once you’ve gone past zero. That description is already an algorithm: the recursive case does the printing and calls itself with a smaller number, and the base case is the point where there is nothing left to print.

Under the hood, each call to a recursive function creates a new stack frame — a block of memory holding that call’s local variables and the point in the code it should return to. When factorial(4) calls factorial(3), Python pauses factorial(4), pushes a new frame for factorial(3) onto the call stack, and only resumes factorial(4) once factorial(3) has returned a value. This is why recursion “unwinds” from the bottom up: the deepest call (the base case) finishes first, and each waiting frame above it completes in turn, using the value the frame below it returned. This stack of waiting frames is also the reason recursion has a memory cost proportional to how deep it goes, and why Python enforces a recursion depth limit (around 1000 frames by default) to stop a runaway recursive function from crashing the interpreter.

One Python-specific fact worth knowing: unlike some functional languages, Python does not perform tail-call optimization. Even if a recursive call is the very last operation in a function, Python still pushes a full new stack frame for it. Rewriting a function to be “tail recursive” does not save memory in Python the way it might in Scheme or Haskell. The only reliable ways to bound stack usage here are to convert the algorithm to an iterative loop with an explicit stack, or to reduce how deep the recursion needs to go in the first place (for example, halving the problem each call instead of shrinking it by one).

Time and Space Complexity

The complexity of a recursive function depends on two things: how many calls it makes, and how much work each call does outside of its recursive calls. It helps to picture a recursion tree — one node per call. The time complexity is roughly the number of nodes times the work per node, while the space complexity (for the call stack) is the depth of the deepest branch, since only the frames along the current path are in memory at once, not the whole tree.

Function	Time	Space (call stack)	Why
factorial(n)	O(n)	O(n)	One call per value from n down to 0: n total calls, each doing O(1) work besides its recursive call; the stack holds up to n waiting frames at the deepest point.
recursive_sum(list)	O(n)	O(n)	One call per element of the list; each frame does O(1) work besides the recursive call, and up to n frames sit on the stack at once.
Naive recursive fibonacci(n)	O(2^n)	O(n)	Each non-base call spawns two more calls, so the tree has roughly 2^n nodes, but the stack only ever holds the single deepest path at a time, which has depth n.

Examples

Example 1: Factorial

Factorial is the classic first recursive function: n! is defined as n * (n-1)!, with 0! defined as 1. That definition translates almost directly into code.

def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)


def main() -> None:
    result = factorial(5)
    print(f"5! = {result}")


if __name__ == "__main__":
    main()

Output:

5! = 120

Tracing it: factorial(5) calls factorial(4), which calls factorial(3), and so on down to factorial(0), which hits the base case and returns 1 without recursing further. Then each paused call multiplies its own n by the value it got back: factorial(1) returns 1 * 1 = 1, factorial(2) returns 2 * 1 = 2, factorial(3) returns 3 * 2 = 6, factorial(4) returns 4 * 6 = 24, and finally factorial(5) returns 5 * 24 = 120.

Example 2: Summing a List Recursively

Many operations that look like loops can be written recursively by peeling off one element at a time and letting the recursive call handle “everything else.”

def recursive_sum(numbers: list[int]) -> int:
    if not numbers:
        return 0
    return numbers[0] + recursive_sum(numbers[1:])


def main() -> None:
    values = [4, 2, 9, 7, 1]
    total = recursive_sum(values)
    print(f"Sum of {values} is {total}")


if __name__ == "__main__":
    main()

Output:

Sum of [4, 2, 9, 7, 1] is 23

The base case is an empty list, which sums to 0. Each recursive call adds the first element to the sum of the rest: 4 + (2 + (9 + (7 + (1 + 0)))), which is 4 + 2 + 9 + 7 + 1 = 23. Note that slicing with numbers[1:] creates a new list each call, which is fine for teaching but adds O(n) copying work per call — passing a starting index instead would be more efficient on large lists.

Example 3: Naive Recursive Fibonacci (and Why It’s Slow)

The Fibonacci sequence is defined recursively (fib(n) = fib(n-1) + fib(n-2)), which makes it tempting to implement exactly as written — but this reveals how expensive redundant recursive calls can get.

def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


def main() -> None:
    for i in range(8):
        print(f"fibonacci({i}) = {fibonacci(i)}")


if __name__ == "__main__":
    main()

Output:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13

Each call to fibonacci(n) for n > 1 makes two more calls, and those calls overlap: computing fibonacci(5) recomputes fibonacci(3) twice and fibonacci(2) three times, from scratch, every time. That redundancy is why this version is O(2^n) instead of O(n) — by fibonacci(30) it is already noticeably slow. The fix, caching each subproblem’s answer the first time it’s computed (memoization) so repeated calls are O(1) lookups, is covered in the Dynamic Programming section; the takeaway here is that a recursive definition being correct does not mean it’s efficient.

How It Works Step by Step

To see the call stack build up and unwind concretely, trace factorial(4) frame by frame:

Step	Call	Action
1	factorial(4)	Not the base case; calls factorial(3) and waits.
2	factorial(3)	Not the base case; calls factorial(2) and waits.
3	factorial(2)	Not the base case; calls factorial(1) and waits.
4	factorial(1)	Not the base case; calls factorial(0) and waits.
5	factorial(0)	Base case reached: returns 1 immediately, no further calls.
6	factorial(1) resumes	Receives 1, computes 1 * 1, returns 1.
7	factorial(2) resumes	Receives 1, computes 2 * 1, returns 2.
8	factorial(3) resumes	Receives 2, computes 3 * 2, returns 6.
9	factorial(4) resumes	Receives 6, computes 4 * 6, returns 24.

Steps 1–4 are the stack growing (“winding up”); at its peak, four frames are stacked, each paused mid-multiplication and waiting on the call below it. Step 5 is the base case, the only step that doesn’t recurse. Steps 6–9 are the stack shrinking (“unwinding”), with each frame finishing its pending multiplication using the value the level below just handed back.

Common Mistakes

Mistake 1: Missing or Incorrect Base Case

If a recursive function never reaches a condition that stops the recursion, every call keeps spawning another call until Python’s recursion limit is hit and a RecursionError is raised. This countdown function looks reasonable but never checks when to stop:

def countdown(n: int) -> None:
    print(n)
    countdown(n - 1)


countdown(5)

Output:

5
4
3
2
1
0
-1
... (keeps printing decreasing integers until the recursion limit is hit)
RecursionError: maximum recursion depth exceeded

There is no base case at all, so n keeps decreasing past 0 into negative numbers forever — in practice, until Python’s stack depth limit stops it with an error. The fix is to add a condition that stops the recursion once n has gone far enough:

def countdown(n: int) -> None:
    if n < 0:
        return
    print(n)
    countdown(n - 1)


def main() -> None:
    countdown(3)


if __name__ == "__main__":
    main()

Output:

3
2
1
0

Now every call moves strictly toward the base case (n < 0), so the recursion is guaranteed to terminate.

Mistake 2: Mutable Default Arguments in Recursive Accumulators

It’s tempting to give an accumulator parameter a default value so callers don’t have to pass one in, but Python evaluates default argument values once, when the function is defined — not once per call. If that default is a mutable object like a list, every call that relies on the default shares the same list, and mutations from one call leak into the next:

def collect_powers_of_two(n: int, acc: list[int] = []) -> list[int]:
    if n == 0:
        return acc
    acc.append(2 ** n)
    return collect_powers_of_two(n - 1, acc)


def main() -> None:
    first = collect_powers_of_two(3)
    second = collect_powers_of_two(2)
    print(f"first call: {first}")
    print(f"second call: {second}")


if __name__ == "__main__":
    main()

Output:

first call: [8, 4, 2]
second call: [8, 4, 2, 4, 2]

The second call should logically start from an empty list, but it silently inherits the leftover contents from the first call, because both calls share the one default list object created when collect_powers_of_two was defined. The fix is to default the parameter to None and create a fresh list inside the function body on each call:

def collect_powers_of_two(n: int, acc: list[int] | None = None) -> list[int]:
    if acc is None:
        acc = []
    if n == 0:
        return acc
    acc.append(2 ** n)
    return collect_powers_of_two(n - 1, acc)


def main() -> None:
    first = collect_powers_of_two(3)
    second = collect_powers_of_two(2)
    print(f"first call: {first}")
    print(f"second call: {second}")


if __name__ == "__main__":
    main()

Output:

first call: [8, 4, 2]
second call: [4, 2]

Now each top-level call gets its own fresh list, and the two calls no longer interfere with each other.

Best Practices

• Write the base case first, and double-check that every recursive call passes an input strictly closer to it — a smaller number, a shorter list, a smaller sub-tree.
• Reach for recursion when the problem has a naturally recursive structure (trees, graphs, divide-and-conquer, combinatorial search/backtracking); prefer a plain loop for simple linear processing, since it avoids the per-call stack-frame overhead and Python’s recursion depth limit.
• Be aware of Python’s default recursion limit (sys.getrecursionlimit(), usually around 1000); for inputs that could recurse deeper than that, rewrite the algorithm iteratively with an explicit stack rather than raising the limit, which just delays the crash.
• Never give a recursive helper function a mutable default argument (a list, dict, or set); default it to None and create the mutable object inside the function body.
• If a recursive function recomputes the same subproblem many times (like naive Fibonacci), cache results (memoization) or convert it to a bottom-up dynamic programming solution instead of accepting exponential runtime.
• Remember Python does not optimize tail calls, so a “tail recursive” style function still uses O(depth) stack space — it is not a free way to avoid stack growth here.

Practice Exercises

1. Sum of digits. Write a recursive function sum_digits(n: int) -> int that returns the sum of the decimal digits of a non-negative integer, e.g. sum_digits(1234) should return 10. Hint: the base case is when n is a single digit (n < 10), and the recursive case can use n % 10 for the last digit and n // 10 for the rest.

2. Palindrome check. Write a recursive function is_palindrome(s: str) -> bool that returns whether s reads the same forwards and backwards, without using slice-reversal tricks like s[::-1]. Instead, compare the first and last characters and recurse on the substring between them. is_palindrome("racecar") should return True and is_palindrome("hello") should return False.

3. Fast power (interview-style). Write a recursive function power(base: int, exponent: int) -> int that computes base ** exponent for a non-negative exponent in O(log exponent) time, using the identity that when exponent is even, base^exponent = (base^(exponent // 2))^2. power(2, 10) should return 1024.

Summary

• A recursive function must have a base case (stops the recursion) and a recursive case that always moves strictly closer to it, or it will recurse forever and raise a RecursionError.
• Each call pushes a new stack frame; the call stack unwinds from the base case back up to the original call, which is why the deepest call’s work finishes first.
• Time complexity depends on how many calls are made and the work per call (e.g. O(n) for factorial and list summation); space complexity for the call stack is the maximum recursion depth (also O(n) for those examples).
• Naive recursive Fibonacci is O(2^n) because it recomputes the same subproblems repeatedly — a sign to consider memoization or an iterative/dynamic-programming rewrite.
• Python does not optimize tail calls, and its default recursion limit is around 1000 frames — deep recursion should often be rewritten iteratively.
• Never use a mutable default argument in a recursive accumulator function; default to None and initialize the mutable object inside the function body.