beginnerintermediateadvanced

Data Structures & Algorithms · Section 8

Recursion

Level: beginner
Read: 85 min
Concepts: 12

What actually stops a recursive function (a reachable base case) and what it costs (one stack frame per unreturned call), the shapes recursion takes on arrays, strings, and mutually-calling functions, and memoization — the exact bridge from plain recursion into dynamic programming.

What is true here

A base case only stops recursion if every recursive call moves the input strictly closer to it.
Recursion depth is real stack memory — Python's default recursion limit exists because each frame costs actual space.
Python doesn't optimize tail calls, so tail and head recursion cost the same stack space, unlike in languages that do.
Memoization is top-down dynamic programming — caching a recursive call's result the first time, then reusing it every time after.

What you will be able to do

Write a recursive function with a reachable base case and a strictly-shrinking recursive case
Explain why a correct recursive function can still crash from depth alone, and convert it to iteration when that matters
Trace a recursion tree by hand to find repeated subproblems
Memoize a recursive function by hand, and with @functools.lru_cache

Concepts

What makes recursion work, what it costs, the shapes it takes, and memoization as the bridge to dynamic programming.

Base case and recursive case

corebeginner

Every recursive function needs a base case that returns directly, with no further recursive call, and a recursive case that calls itself on a smaller version of the same problem — the base case is what stops the calls.

Think of it as

A recursive function is a promise: 'hand me a smaller version of this problem and I already know how to combine your answer into mine — that is the recursive call. Once the problem is small enough, I can answer immediately, with no help — that is the base case.' Skip the base case, or never actually shrink the input, and the promise never resolves.

What we're doing: Compute a factorial recursively, with the base case stopping the recursion at n <= 1.

factorial.pypython

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))
print(factorial(0))

2: n <= 1 (not just n == 0) covers both the natural stopping point and the smallest valid input in one check.
4: Each call passes n - 1 — strictly smaller than n — guaranteeing the base case is eventually reached.

Output

120
1

Why this works: factorial(5) expands to 5 * 4 * 3 * 2 * 1 = 120. factorial(0) hits the base case immediately, returning 1 with no recursive call at all.

A base case that exists but is never reachable, because the input never shrinks

Wrong

python

def factorial_wrong(n):
    if n == 0:
        return 1
    return n * factorial_wrong(n)  # forgot n - 1


print(factorial_wrong(5))

Better

python

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

What you see: factorial_wrong(5) raises RecursionError: maximum recursion depth exceeded — it never returns at all.

Why: The recursive call passes n unchanged instead of n - 1, so every call sees the exact same n. n == 0 is a real base case, but it is never reached from n = 5, since n never gets any smaller.

Fibonacci NumbereasyLeetCode
Two base cases (n <= 1) and one recursive case — the smallest complete example of the pattern beyond factorial.
Pow(x, n)mediumLeetCode
The base case is n == 0 (return 1); the recursive case can halve n each call instead of just subtracting 1, for O(log n) depth instead of O(n).

Remember: A base case only stops recursion if every recursive call actually moves the input closer to it — a base case that is never reached is no different from having none at all.

Was this helpful?

The call stack, and how recursion depth relates to space complexity

corebeginner

Each recursive call pushes a new frame onto the call stack, holding that call's local variables, and the frame is only popped once the call returns — so recursion depth IS the function's space complexity, not just an implementation detail.

Think of it as

Picture a stack of plates, one added per call, each holding that call's own copy of its arguments and locals. Nothing is removed until the top plate's function actually returns. A chain of n nested calls, none of which have returned yet, needs O(n) space for their stacked frames — exactly like an array of size n would.

What we're doing: Show that recursion depth grows with input size, and that a genuinely deep recursion crashes even when the logic is correct.

recursion_depth.pypython

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


big_list = list(range(5000))
try:
    print(recursive_sum(big_list))
except RecursionError as e:
    print(f"RecursionError: {e}")

8: A call is not popped until the ENTIRE list has been consumed — recursion depth here equals the list length, 5000.

Output

RecursionError: maximum recursion depth exceeded

Why this works: recursive_sum's logic is completely correct — it would compute the right total, given enough stack. But each of the 5000 calls needs its own frame, and 5000 stacked frames exceeds Python's default recursion limit before the base case is ever reached.

Reaching for recursion on input whose size is not bounded, instead of iteration

Wrong

python

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


print(recursive_sum(list(range(5000))))

Better

python

def iterative_sum(nums):
    total = 0
    for x in nums:
        total += x
    return total


print(iterative_sum(list(range(5000))))

What you see: recursive_sum crashes with RecursionError on a 5,000-element list; iterative_sum handles it (and lists far larger) without issue.

Why: A for loop reuses the SAME stack frame for every element — O(1) stack space regardless of list length. Recursion trades that for one frame per element, which is exactly what makes it depth-limited in the first place.

Maximum Depth of Binary TreeeasyLeetCode
A balanced tree's recursion depth is only O(log n) — a concrete case where recursion depth is much smaller than input size.
Reverse Linked ListeasyLeetCode
A recursive solution has depth equal to list length, exactly like recursive_sum above — the iterative version is the standard fix for long lists.

Remember: Recursion depth is real memory, one stack frame per unreturned call — a correct recursive function can still crash purely from depth, which is a capacity problem, not a logic bug.

Was this helpful?

Tracing a recursion tree by hand

standardbeginner

Drawing every recursive call as a node, connected to the calls it makes and the value it returns, turns an abstract recursive function into a picture that can actually be checked by eye.

Think of it as

Write the initial call at the top. Every time it makes a recursive call, draw a new node below it and connect them. Once a node hits its base case, write its return value directly on it. Then read the tree bottom-up: each non-base node's return value is computed from its children's already-known values — the same order the real call stack unwinds in.

What we're doing: Trace naive recursive Fibonacci and count exactly how many calls it makes, to see the repeated work directly.

trace_fib.pypython

call_count = 0


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


result = fib(4)
print(result, call_count)

4: call_count increments on EVERY call, base case included — this is the total node count of the recursion tree.
7: fib(n - 1) and fib(n - 2) are two separate subtrees — fib(2) gets computed once inside fib(3) and again inside fib(4) itself, from scratch each time.

Output

3 9

Why this works: fib(4) = 3, matching the sequence 0, 1, 1, 2, 3. But reaching that answer took 9 total calls for an input of just 4 — fib(2) alone is computed twice (once inside fib(3), once inside fib(4)) because neither call remembers the other did the same work.

Remember: Tracing a call tree by hand exposes exactly which subproblems get solved more than once — that repeated work is precisely what memoization exists to eliminate.

Head recursion vs tail recursion (Python doesn't optimize tail calls)

standardbeginner

In tail recursion, the recursive call is the very last thing the function does. In head recursion, work happens after the recursive call returns. Python optimizes neither into a loop, so both cost the same stack space.

Think of it as

Ask: once the recursive call returns, is there anything left to compute in THIS frame? If no — just hand back whatever the call returned — that is tail recursion. If yes, like multiplying the call's result by n, that is head recursion, since the multiplication happens after the call. Some languages turn a tail call into a plain loop under the hood, reusing one frame; CPython deliberately does not.

What we're doing: Compare a tail-recursive and a head-recursive factorial, and confirm neither escapes the recursion limit.

head_vs_tail.pypython

def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)


def factorial_head(n):
    if n <= 1:
        return 1
    return n * factorial_head(n - 1)


print(factorial_tail(10), factorial_head(10))

for name, fn in [("tail", factorial_tail), ("head", factorial_head)]:
    try:
        fn(3000)
        print(f"{name}: completed")
    except RecursionError:
        print(f"{name}: RecursionError")

4: The recursive call is the entire return statement — nothing runs after it comes back. This is tail recursion.
9: n * factorial_head(n - 1) has to wait for the recursive call to return before the multiplication can happen — this is head recursion.

Output

3628800 3628800
tail: RecursionError
head: RecursionError

Why this works: Both functions agree on the small case (10! = 3628800). At depth 3000, both hit RecursionError identically — proof that being tail-recursive bought no extra depth in CPython, unlike in a language that performs tail-call optimization.

Remember: A tail call is one with nothing left to do after it returns — but in CPython that fact changes nothing about stack usage; both styles cost one frame per call.

Was this helpful?

Converting recursion to iteration

standardbeginner

Any recursive function can be rewritten as a loop with an explicit stack — trading the call stack's automatic bookkeeping for a manual one that never hits Python's recursion limit.

Think of it as

Where recursion says 'call myself and let Python remember where I was,' iteration says 'push what I need to remember onto my OWN list, and pop it back off in a loop.' The manual stack lives on the heap, not the interpreter's call stack, so it can grow far larger than sys.getrecursionlimit() would allow.

What we're doing: Flatten an arbitrarily nested list both recursively and iteratively, with an explicit stack standing in for the call stack.

flatten.pypython

def flatten_recursive(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten_recursive(item))
        else:
            result.append(item)
    return result


def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()
            continue
        if isinstance(item, list):
            stack.append(iter(item))
        else:
            result.append(item)
    return result


data = [1, [2, 3, [4, [5, 6]], 7], 8]
print(flatten_recursive(data))
print(flatten_iterative(data))

11: stack holds one ITERATOR per level of nesting still being worked through — this is the manual replacement for the call stack.
15: A finished iterator (StopIteration) is exactly the equivalent of a recursive call's base case returning — pop it and continue with whatever called it.
19: Finding another nested list pushes a NEW iterator, exactly like a recursive call would descend one level deeper.

Output

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

Why this works: Both versions flatten the same nested structure to the same 8-element list. The recursive version reads more directly, but its depth grows with nesting depth; the iterative version bounds stack usage to O(1) frames, no matter how deeply data is nested.

Remember: The explicit stack in an iterative rewrite replaces the call stack entirely — it has to hold everything a stack frame would have, not just the input.

Recursion on arrays/strings (divide the input, recurse on a piece)

corebeginner

A recursive function on an array or string typically peels off one element or splits the input in half, then recurses on what remains — the base case is whatever input is too small to divide any further.

Think of it as

Ask: if I already had the answer for everything except the first element (or half), how would I combine it with that one piece to get the full answer? That combining step is the recursive case. The base case is the input too small to split — usually empty or a single element.

What we're doing: Reverse a string recursively by peeling off one character at a time.

reverse_string.pypython

def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]


print(reverse_string("hello"))

2: <= 1 covers BOTH the empty string and a single character — either way, there is nothing left to reverse.
3: The first character is moved to the end, after everything else has already been reversed.

Output

olleh

Why this works: "hello" peels off 'h', recurses on "ello", and appends 'h' after the recursive call returns "olle" — giving "olle" + "h" = "olleh".

A base case that only checks for length 1, missing the empty string

Wrong

python

def reverse_string_wrong(s):
    if len(s) == 1:
        return s
    return reverse_string_wrong(s[1:]) + s[0]


print(reverse_string_wrong(""))

Better

python

def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

What you see: reverse_string_wrong("") raises RecursionError: maximum recursion depth exceeded, instead of returning "".

Why: len(s) == 1 is never true for an empty string, so the base case is skipped — and slicing an empty string ("")[1:] always produces another empty string, so the input never changes between calls.

Reverse StringeasyLeetCode
The example above, though the accepted in-place solution typically uses two pointers instead — worth comparing both.
Binary SearcheasyLeetCode
The "split in half" style of this pattern — recursion depth is O(log n) instead of O(n).

Remember: Peeling one element gives O(n) recursion depth; splitting in half gives O(log n) — check the base case covers EVERY input small enough to stop on, empty included.

Recursion on trees/graphs (natural fit)

referencebeginner

A tree or graph node's children are themselves smaller trees or graphs, so a recursive function that processes 'this node, then each child' fits the data's shape directly — the base case is a node with no children left to visit.

Remember: A tree/graph's recursive structure mirrors its data structure directly — depth follows height, not total node count, and a graph additionally needs a visited set to avoid looping on a cycle.

Mutual recursion

standardbeginner

Mutual recursion is two or more functions that call each other instead of calling themselves — A calls B, B calls A — with the base case reached by whichever function actually gets there.

Think of it as

Trace it exactly like ordinary recursion, just switching which function's code is being read each time a call crosses over. The call stack does not care that the frames alternate between two different functions — it is still one continuous chain, and it still needs a base case that eventually stops the alternation.

What we're doing: Determine whether a number is even or odd using two functions that call each other.

mutual_recursion.pypython

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)


def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)


print(is_even(10), is_odd(10))
print(is_even(7), is_odd(7))

3: is_even hands off to is_odd on a smaller number — the two functions take turns, but the input still shrinks by 1 every call.
9: is_odd hands back to is_even — the base case (n == 0) is only ever reached by whichever function the countdown lands on.

Output

True False
False True

Why this works: 10 is even: is_even(10) → is_odd(9) → is_even(8) → ... → is_even(0) → True. The chain for 7 ends one step later, on is_odd(0) → False, so is_even(7) is False and is_odd(7) is True.

Remember: Mutual recursion is one continuous call chain split across two function bodies — it still needs exactly one thing ordinary recursion needs: a base case the alternation eventually reaches.

Memoization as the bridge from recursion to dynamic programming

corebeginner

Memoization caches a recursive function's result for each distinct set of arguments, so a subproblem reached more than once is solved only the first time — turning an exponential-time recursion into a polynomial one.

Think of it as

Before doing any work, check a cache keyed by the arguments. If the answer is already there, return it immediately, with no further recursive calls. If not, compute it the normal recursive way, but store the result before returning — so every FUTURE call with the same arguments is an O(1) lookup instead of repeating an entire subtree of calls.

What we're doing: Memoize recursive Fibonacci and confirm the cache actually gets checked before recursing, not just written to afterward.

memoization.pypython

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]


print(fib_memo(30))

4: cache=None as the default (not cache={}) avoids Python's mutable-default-argument pitfall — a fresh dict is made for every top-level call.
5: Checking `n in cache` BEFORE recursing is what actually short-circuits repeated work — computing without this check first would still visit the whole exponential tree.

Output

Why this works: fib_memo(30) computes instantly because every fib(k) for k from 0 to 30 is computed exactly once and reused — unlike naive recursion, which would revisit the same k many times over.

Storing a result in the cache without ever checking the cache before recursing

Wrong

python

call_count = 0


def fib_memo_wrong(n, cache=None):
    global call_count
    call_count += 1
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    result = fib_memo_wrong(n - 1, cache) + fib_memo_wrong(n - 2, cache)
    cache[n] = result  # stored, but never checked before recursing
    return result


fib_memo_wrong(20)
print(call_count)

Better

python

call_count = 0


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


fib_memo_right(20)
print(call_count)

What you see: fib_memo_wrong(20) makes 21,891 calls; fib_memo_right(20), differing only by checking the cache first, makes 39.

Why: Writing to the cache is only half of memoization — without a lookup before recursing, every call still triggers the same full recursive tree as no caching at all. The cache dict fills up, but nothing ever reads from it.

Fibonacci NumbereasyLeetCode
Exactly the example above — a dict cache checked before every recursive call.
Climbing StairseasyLeetCode
The same recurrence shape as Fibonacci in disguise — memoizing it is the identical fix for the identical exponential blowup.

Remember: Memoization needs BOTH halves: check the cache before recursing, and write to it before returning — storing a result without ever checking for one first buys nothing.

Was this helpful?

Python specifics

The interpreter-level facts about recursion that are specific to Python, not recursion in general.

Python's default recursion limit and sys.setrecursionlimit

standardbeginner

sys.getrecursionlimit() reports how many stacked calls Python allows before raising RecursionError — a safety net, not a hardware limit — and sys.setrecursionlimit(n) can raise it, but usually just delays a crash an iterative rewrite would avoid entirely.

Think of it as

The limit exists because each stacked frame uses real memory in the interpreter's underlying stack. Raise the limit far enough with genuinely deep recursion, and instead of a clean RecursionError, the process can crash outright — worse, and no longer even a normal Python exception. Reaching for setrecursionlimit should prompt the question 'should this be iterative or memoized instead?' before touching the knob.

What we're doing: Read the current recursion limit, then confirm a lowered limit is enforced.

recursion_limit.pypython

import sys

print(sys.getrecursionlimit())

def count_down(n):
    if n == 0:
        return 0
    return count_down(n - 1)

original_limit = sys.getrecursionlimit()
sys.setrecursionlimit(50)
try:
    count_down(100)
except RecursionError as e:
    print(f"RecursionError: {e}")
sys.setrecursionlimit(original_limit)

5: This interpreter's default is 1000 — printed directly rather than assumed.
12: Lowering the limit to 50 and recursing 100 deep is guaranteed to trip it — this proves the limit is actually enforced, not just documented.

Output

1000
RecursionError: maximum recursion depth exceeded

Why this works: The default limit (1000) is comfortably above count_down(100)'s needs, so the first call would succeed silently. Lowering it to 50 makes the same 100-deep recursion fail immediately, confirming the limit is a live, adjustable check — not a fixed constant.

Remember: sys.setrecursionlimit moves the ceiling for THIS process only, at the cost of real crash risk if pushed too far — it never removes the fact that depth still scales with input size.

Was this helpful?

`functools.lru_cache` for automatic memoization

standardbeginner

@functools.lru_cache wraps a function so Python automatically caches its return value per distinct set of arguments — the same speedup as a hand-written memoization dict, with one decorator line.

Think of it as

Think of the decorator as inserting the 'check the cache, then store in the cache' scaffolding automatically, keyed by the exact arguments passed. Calling the decorated function again with arguments it has already seen skips the function body entirely and returns the cached value straight away.

What we're doing: Memoize recursive Fibonacci with one decorator, and confirm the cache actually filled from cache_info().

lru_cache_fib.pypython

from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(30))
print(fib.cache_info())

3: One decorator replaces the entire hand-written cache dict and the two if-checks around it from a manual memoization implementation.

Output

832040
CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)

Why this works: fib(30) needs fib(0) through fib(30) — 31 distinct arguments, so 31 misses (each computed once) and 28 hits (every time an already-computed value like fib(15) is asked for again from a different branch of the recursion).

Remember: @lru_cache(maxsize=None) is a hand-written memoization dict in one line — confirm it actually helped with .cache_info(), not just by assuming from speed.

Recognizing RecursionError vs a logic bug

referencebeginner

A RecursionError means the base case was never reached, or the input never actually shrank — it says nothing by itself about whether the logic would have been correct given enough stack.

Remember: RecursionError means "never reached the base case, or never got closer to it" — diagnose that specifically before assuming anything else about the function is wrong.

Was this helpful?

Spotted a mistake on this page? Tell us.

Read Sheet