RecursionRecursion

01Why it exists

Reach for it when you see:A structure that contains the same structure, no telling how many levels deep, shrinking the problem a little turns it into the same problem, tree-shaped data.

02The core idea

Recursion is a function calling itself, but the part that actually matters is the way of thinking: take a problem of size n and build its answer out of the answer to a smaller version of the same problem. You are responsible for exactly two things — how to answer the smallest problem directly (the base case), and how to assemble the big answer from the small one (the recursive case).

While the program runs, every call puts a frame on the call stack, remembering this level's arguments and where to return once it has an answer. After the descent reaches the base case, those frames pop one by one, passing the answer back up. That is why recursion costs at least O(depth) space, and why recursing too deep overflows the stack.

What trips up beginners most is trying to trace what every level is doing. Don't. Trust that the recursive call returns the right answer and only check that your own level uses it correctly. This is the recursive leap of faith, and it is mathematical induction in code form.

03The algorithm

1. 1Define what the function means: factorial(n) returns n factorial. State the meaning clearly, because that is what you will later be trusting.
2. 2Write the base case: the smallest situation, the one you can answer outright. n == 1 returns 1. With no base case the recursion never ends.
3. 3Write the recursive case: assume factorial(n - 1) is already correct, and then factorial(n) is just n * factorial(n - 1).
4. 4Check that every recursive call moves toward the base case (n gets smaller, the list gets shorter, the tree goes one level down), or it will never stop.
5. 5Estimate the depth: factorial recurses n deep, anything that halves recurses log n deep. When the depth gets too large, switch to iteration or an explicit stack.

04Interactive demo

Step through factorial(4). On the left is the line currently executing; on the right is the call stack, pushing one frame at a time on the way down and returning one answer at a time once the base case is reached.

1def factorial(n):
2    if n == 1:
3        return 1
4    return n * factorial(n - 1)

05Code

The three examples cover the three shapes recursion takes — a number shrinking, a list getting shorter, and a tree going one level down — with the iterative version at the end for comparison.

def factorial(n):
    if n == 1:                      # base case: the smallest problem, answered outright
        return 1
    return n * factorial(n - 1)     # recursive case: hand it to a smaller copy of yourself


def total(items):
    # Sum of a list: the first element + the sum of the rest
    if not items:
        return 0
    return items[0] + total(items[1:])


def folder_size(folder):
    # Folder size = every file in it + every subfolder in it
    size = sum(f.size for f in folder.files)
    for sub in folder.subfolders:
        size += folder_size(sub)    # a subfolder has exactly the same shape as this folder
    return size


def factorial_iter(n):
    # The iterative version of the same thing: no call stack, O(1) space
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

06Practice

• LeetCode 344Reverse String (do it recursively)Easy
• LeetCode 509Fibonacci NumberEasy
• LeetCode 206Reverse Linked List (the recursive version)Easy
• LeetCode 70Climbing Stairs (write the recursion first, and feel why it is slow)Easy
• LeetCode 779K-th Symbol in GrammarMedium