Recursion Field Notes

0Why recursion exists

Recursion is when a function calls itself, usually with a different (smaller) input. A function that does this is a recursive function. It breaks a problem into smaller sub-problems of the same shape, and then solves them in reverse order: the smallest one is finished first, and the biggest one is finished last.

Every recursive function has exactly two parts:

• Base case: the input is so small that you answer directly, with no further call. Without it the function never stops.
• Recursive case: the function calls itself on a smaller input and uses that result to build its own answer.

There are two shapes. One-branch recursion makes one recursive call per step (factorial, lesson 8). Multi-branch recursion makes two or more (fibonacci, lesson 9), which draws a tree of calls. It is usually possible to convert recursion to iteration and back. Sometimes the loop is simpler, sometimes the recursion is. Trees and graphs, which come later in the course, are where recursion is the natural choice.

1One branch: factorial

n! as a smaller copy of itself

n factorial, written n!, is the product of all whole numbers from n down to 1: n! = n × (n-1) × (n-2) × ... × 1. Example: 5! = 5 × 4 × 3 × 2 × 1 = 120.

Look at the same product again: 5! = 5 × 4!, and 4! = 4 × 3!, and so on. Each factorial is "n times a smaller factorial". That is the recursive case. The chain has to end somewhere: 1! = 1 and, by definition, 0! = 1. That is the base case.

# Recursive implementation of n! (n-factorial) calculation
def factorial(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return 1
    # Recursive case: n! = n * (n - 1)!
    return n * factorial(n - 1)

Two things to notice. The base case comes first, so it is checked before any new call. And the recursive call is on a smaller input (n - 1), so every call moves toward the base case.

Trace factorial(5): down, then up

factorial(5) wants to return 5 * factorial(4). It cannot finish until factorial(4) answers. So it waits, and factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1). That last one is the base case and returns 1 without calling anyone. Now the waiting calls finish in reverse: 2 × 1 = 2 (that is 2!), 3 × 2 = 6, 4 × 6 = 24, 5 × 24 = 120.

Read the table top to bottom for the calls, then bottom to top for the returns. Step ⑤ returns first; step ① returns last. That is what "solve the sub-problems in reverse order" means.

See it happen: a traced version

Add a depth argument and print with indentation. This is the single best way to build intuition; do it once for every recursive function you write this week.

def factorial_traced(n, depth=0):
    pad = "    " * depth
    print(f"{pad}factorial({n}) called")
    if n <= 1:
        print(f"{pad}base case -> return 1")
        return 1
    sub = factorial_traced(n - 1, depth + 1)   # wait here until the smaller call returns
    print(f"{pad}factorial({n}) = {n} * {sub} = {n * sub}")
    return n * sub

factorial_traced(5)
# factorial(5) called
#     factorial(4) called
#         factorial(3) called
#             factorial(2) called
#                 factorial(1) called
#                 base case -> return 1
#             factorial(2) = 2 * 1 = 2
#         factorial(3) = 3 * 2 = 6
#     factorial(4) = 4 * 6 = 24
# factorial(5) = 5 * 24 = 120

2The call stack: where the space goes

factorial creates no list, no dictionary, nothing. So why is its space O(n)? Because recursion uses an implicit stack: the function call stack that the language keeps for you. Each call gets a stack frame holding its own n and the place to return to. That is how "return from this call to the previous one" works at all. factorial(5) has five frames alive at once, so the stack holds n frames: O(n) space even though you wrote no data structure.

Stack overflow and Python's recursion limit

The call stack has a fixed size. Go too deep and you get a stack overflow. Python guards this with a depth limit, 1000 frames by default, and raises RecursionError when you cross it. You can raise the limit for a deep but correct recursion (a linked list of 5000 nodes, for example). It does not fix a missing base case; it only delays the crash.

import sys
sys.getrecursionlimit()          # 1000 by default in CPython
sys.setrecursionlimit(10_000)    # allow deeper recursion (use with care)

factorial(3000)                  # ok now; RecursionError under the default limit

def no_base_case(n):
    return n * no_base_case(n - 1)   # 5, 4, 3, ..., -900, ... never stops

no_base_case(5)   # RecursionError: maximum recursion depth exceeded

Iteration vs recursion

The same product with a loop. NeetCode's version stores the running answer in res and decrements n until it reaches 1:

n = 5
res = 1
while n > 1:
    res = res * n
    n -= 1
# res is 120, n is 1

# the same thing as a function
def factorial_iter(n):
    res = 1
    while n > 1:
        res = res * n
        n -= 1
    return res

For factorial the loop is simpler and cheaper. That is not always true. For trees, where every node has two children, the recursive version is usually a few lines and the loop needs you to manage your own stack. Rule: iterative is more space-efficient (no call stack); recursive is often shorter and clearer for branching problems.

3Two branches: fibonacci

Multi-branch recursion, where a function calls itself more than once, is more common in practice than one-branch. The classic example is the Fibonacci sequence. It starts 0, 1, and each next number is the sum of the two before it:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Base cases: F(0) = 0 and F(1) = 1. Recursive case: F(n) = F(n-1) + F(n-2). A formula that defines a value in terms of smaller values of itself is called a recurrence relation: fib(n) = fib(n-1) + fib(n-2). You will meet recurrence relations again in dynamic programming.

# Recursive implementation to calculate the n-th Fibonacci number
def fibonacci(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return n
    # Recursive case: fib(n) = fib(n - 1) + fib(n - 2)
    return fibonacci(n - 1) + fibonacci(n - 2)

Note the base case returns n itself, not 1: fibonacci(0) is 0 and fibonacci(1) is 1. The last line calls the function twice. That is a branch factor of two: every call spawns two more, so the calls form a tree instead of a chain.

Trace fibonacci(5): a tree, not a chain

fibonacci(5) = fibonacci(4) + fibonacci(3). Python evaluates the left call first, so fibonacci(4) runs to completion (it calls fibonacci(3) + fibonacci(2), and so on down to 1 or 0) before fibonacci(3) on the right even starts. Then the values come back up: fibonacci(4) = 3, fibonacci(3) = 2, so fibonacci(5) = 5.

Trace table: fibonacci(4), every call and every return

The tree hides the order. This table shows the real order of events for fibonacci(4): 9 calls, 9 returns, and the stack after each event (bottom on the left, top on the right).

Two facts fall out of the table. The stack never holds more than 4 frames (n frames in general), so space is O(n). And F(2) was fully recomputed at step 12 even though step 8 already knew the answer.

Count the calls

A quick experiment before the theory: add a counter.

calls = 0

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

# n:      4    5    10     20
# calls:  9   15   177  21891     roughly doubles every time n grows by 1

Time complexity: count the tree level by level

Look at the tree by levels (rows). Level 0 has 1 node, the root. Each node makes two calls, so level 1 can hold 2 nodes, level 2 can hold 4, level 3 can hold 8. Each level can hold twice the previous one. The deepest level is n (the path n, n-1, n-2, ..., 0 down the left side). So the total number of nodes is at most:

1 + 2 + 4 + 8 + ... + 2^n

This is a geometric series, the same kind you met when a dynamic array doubles its capacity. The last term dominates: the sum is 2^(n+1) - 1, which is less than 2 × 2^n. Drop the constant and the total number of nodes is O(2^n). Each node is one function call that does one addition of two values, O(1) work. So the time complexity is O(2^n).

4Four moves that make recursion routine

The lessons teach factorial and fibonacci. Interviews test whether you can set up any recursion cleanly, and whether you know when to leave it. These four moves cover that.

Move 1: Base case first (the checklist)

Before typing the recursive call, answer three questions in this order. Write the base case first, physically at the top of the function.

1. What is the smallest input? Empty list, n = 0, None node, l >= r. Return its answer directly. This is the base case.
2. How do I make the input smaller by one step? n - 1, i + 1, node.next, n // 2. Call yourself on that. Every call must move toward the base case.
3. Given the smaller answer, how do I build mine? n * sub, nums[i] + sub, left + right. Trust that the recursive call returns the right thing. Do not trace it in your head; that is the whole point.

def sum_list(nums, i=0):
    if i == len(nums):              # 1. base case FIRST: nothing left to add
        return 0
    return nums[i] + sum_list(nums, i + 1)   # 2. shrink   3. combine

sum_list([2, 3, 4, 1, 6])   # 16
sum_list([])                # 0  (the base case handles empty input for free)

Move 2: Recursion to iteration

When the interviewer worries about stack depth, or when the recursion is one-branch and the answer is built on the way up, convert to a loop. Two recipes:

• One branch, combine on the way up (factorial, sum): keep the running answer in a variable and loop toward the base case. You saw this in section 2.
• Two branches (fibonacci): go bottom-up. Start from the base cases and build forward, keeping only the last two values. This is the seed of dynamic programming.
• Anything else: replace the call stack with your own list used as a stack. The trees lesson uses this for iterative traversals.

def fib_iter(n):
    a, b = 0, 1                     # a = fib(i), b = fib(i + 1), starting at i = 0
    for _ in range(n):
        a, b = b, a + b             # slide the window one step forward
    return a                        # O(n) time, O(1) space, no stack

def sum_list_iter(nums):
    stack = [0]                     # our own stack replaces the call stack
    total = 0
    while stack:
        i = stack.pop()
        if i == len(nums):           # the old base case
            continue
        total += nums[i]
        stack.append(i + 1)         # the old recursive call
    return total

Move 3: Helper function with an accumulator

Sometimes the public function signature is fixed (LeetCode gives you reverseString(s)) but your recursion needs extra state: an index, two pointers, a running total. Write an inner helper that takes the extra arguments, and call it once. An accumulator is an argument that carries the answer-so-far down the calls, so nothing is left to do on the way up.

def factorial_acc(n):
    def helper(n, acc):
        if n <= 1:
            return acc               # the answer is already finished
        return helper(n - 1, acc * n)  # multiply BEFORE the call, not after
    return helper(n, 1)

def reverseString(s):                # LeetCode 344: reverse list s in place
    def helper(l, r):
        if l >= r:                   # pointers met or crossed: done
            return
        s[l], s[r] = s[r], s[l]
        helper(l + 1, r - 1)
    helper(0, len(s) - 1)

Move 4: Memoization, a one-line preview

The fibonacci tree computed F(2) three times. Memoization means "remember each answer the first time, and look it up after that". In Python it is one decorator, and it turns O(2^n) into O(n) because each distinct n is computed once. The full treatment, including the bottom-up table version, is on the Dynamic Programming page.

from functools import lru_cache

@lru_cache(maxsize=None)          # remembers every (n -> result) pair
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

fib_memo(50)    # 12586269025, instantly. Plain recursion would take ~20 billion calls.

5Big-O summary

Say the time and the space separately, and say where the space comes from ("the call stack") even when there is no data structure.

The last two rows are the ones to memorize. Time counts every node in the call tree. Space counts the height of that tree, because that is the most frames that are ever alive together.

6Mistakes to watch for

7Practice, in this order

For each one, write the base case first, say the time and space out loud, then code it. Several of these have a loop solution; do the recursive version anyway, that is what this page trains.

The recursive reverse for 206, since it is the one people find hardest to picture:

def reverseList(head):
    if head is None or head.next is None:   # base case: empty or single node
        return head
    new_head = reverseList(head.next)       # trust: reverses everything after head
    head.next.next = head                   # the old "next" now points back at head
    head.next = None                        # head becomes the tail
    return new_head                         # same new head is passed all the way up

Your next step today: LeetCode 509. Write the plain recursive version, count the calls for n = 30 with a counter, then add @lru_cache and count again.

8Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.