Recursion for DSA: Base Cases, Call Stack and Memoization

A recursive function solves a problem by calling itself on a smaller version of the same problem. Trees, graphs, sorting algorithms and dynamic programming all lean on recursion, so it is worth getting comfortable with now.

Every recursive function has two parts:

1. a base case: an input small enough to answer directly, with no further calls;
2. a recursive case: break the problem into a smaller one, call yourself, and combine the result.

A first example: factorial#

5! (five factorial) is 5 × 4 × 3 × 2 × 1. Notice that 5! = 5 × 4!: the problem contains a smaller copy of itself.

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

print(factorial(5))
print(factorial(10))

120
3628800

What happens on the call stack#

Each call pauses while it waits for the call below it. Printing as calls start and finish shows the stack growing and then unwinding:

def factorial(n, depth=0):
    pad = "  " * depth
    print(f"{pad}factorial({n}) called")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) returns {result}")
    return result

factorial(4)

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

The deepest call returns first, and each waiting call finishes its multiplication on the way back up. Four levels deep means four frames on the stack: recursion depth n costs O(n) space.

Thinking recursively: trust the smaller call#

The trick is to assume the recursive call already works for the smaller input, and only ask "how do I use its answer?". Summing a list:

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

print(list_sum([2, 4, 6, 8]))

20

"The sum is the first item plus the sum of the rest." You do not need to trace every call to believe it.

When recursion branches: Fibonacci#

Each Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, … The direct recursive version calls itself twice:

calls = 0

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

for n in [10, 20, 25]:
    calls = 0
    value = fib(n)
    print(f"fib({n}) = {value} using {calls} calls")

fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(25) = 75025 using 242785 calls

The calls form a recursion tree that roughly doubles in size with each level, so the time is O(2ⁿ). Most of the work is repeated: fib(20) computes fib(18) twice, fib(17) three times, and so on.

Memoization: remember answers#

Memoization stores each result the first time it is computed and reuses it afterwards. Python's functools.lru_cache does it for you:

from functools import lru_cache

calls = 0

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

print(fib(25), "using", calls, "calls")
print(fib(90))

75025 using 26 calls
2880067194370816120

Each value from 0 to n is now computed once, so the time drops from O(2ⁿ) to O(n). This idea is the start of dynamic programming.

Recursion or a loop?#

Anything recursive can be written with a loop (and an explicit stack if needed). Choose recursion when the problem is naturally recursive (trees, nested structures, divide and conquer, backtracking); choose a loop for simple counting, where it avoids stack overhead and Python's recursion limit (1000 by default).

Common mistakes#

Practice#

calls = 0

def power(base, exp):
    global calls
    calls += 1
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)

print(power(2, 10), power(3, 5))
calls = 0
print(power(2, 1000) == 2 ** 1000, "in", calls, "calls")

1024 243
True in 16 calls

Key takeaway#

Next, the most used data structure of all: Arrays and Dynamic Arrays.