Recursion and Backtracking

The next interview gear

Now that we've covered Trees and Binary Search Trees, Graphs, Dynamic Programming, and even Bit Manipulation, you're ready for one of the most important interview techniques: recursion.

Recursion is how you express:

• “Solve a smaller version of the same problem.”
• “Explore this branch, then come back.”
• “Try every valid possibility without losing track.”

That second idea—explore and come back—is backtracking.

In finance-style interviews, this shows up in problems like generating combinations, searching decision trees, validating constraints, and exploring possible allocations or schedules.

A function that calls itself

A recursive function has two essential parts:

1. Base case: the stopping condition.
2. Recursive case: the smaller version of the same problem.

Think of it like asking: “If I can solve n - 1, how do I solve n?”

For factorial:

• factorial(0) = 1
• factorial(n) = n * factorial(n - 1)

The key is not memorizing factorial. The key is seeing the pattern: reduce the problem until it becomes simple.

```python
def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)  # recursive case

for value in range(6):
    print(value, factorial(value))
```

In a recursive function, what is the main job of the base case?

Recursion uses the call stack

Remember Stacks and Queues? Recursion uses a stack automatically: the call stack.

Each unfinished function call waits for the smaller call to return.

For factorial(3):

factorial(3)
  waits for factorial(2)
    waits for factorial(1)
      waits for factorial(0)

Then answers return upward:

factorial(0) -> 1
factorial(1) -> 1 * 1
factorial(2) -> 2 * 1
factorial(3) -> 3 * 2

Interview note: recursion often has hidden space cost from the call stack. A recursion depth of n usually means O(n) stack space.

Recursion matches tree structure

In Trees and Binary Search Trees, you saw that a tree node can have smaller trees beneath it.

That is exactly the recursive pattern:

• If the node is missing, answer directly.
• Otherwise, solve the left subtree.
• Solve the right subtree.
• Combine the answers.

Here is a classic example: compute the maximum depth of a binary tree.

```python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max_depth(root):
    if root is None:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return 1 + max(left_depth, right_depth)

#       A
#      / \
#     B   C
#    /
#   D
root = Node("A", Node("B", Node("D")), Node("C"))
print(max_depth(root))
```

True or false: A recursive solution always uses less memory than an iterative solution.

Try, explore, undo

Backtracking is recursion for choice problems.

The pattern is:

1. Choose an option.
2. Explore what happens next.
3. Undo the choice.
4. Try another option.

This is useful when an interview problem asks for:

• all subsets
• all permutations
• all valid combinations
• all ways to satisfy constraints

The important move is the undo step. Without it, one branch contaminates the next branch.

```python
def subsets(items):
    result = []
    path = []

    def backtrack(i):
        if i == len(items):
            result.append(path.copy())
            return

        # Choice 1: skip items[i]
        backtrack(i + 1)

        # Choice 2: include items[i]
        path.append(items[i])
        backtrack(i + 1)
        path.pop()  # undo the choice

    backtrack(0)
    return result

print(subsets(["AAPL", "MSFT", "CASH"]))
```

In a typical Python backtracking function, after you do path.append(choice) and recursively explore that choice, what statement usually removes the last choice so the next branch starts clean?

Fill in the blank: _____________

Backtracking builds an invisible tree

Even when there is no explicit tree input, backtracking often creates a decision tree.

For each item, you branch:

include it?
├── no
└── yes

For 3 items, that creates 2^3 = 8 subsets. For n items, it creates 2^n subsets.

This is where your Time and Space Complexity Analysis lesson matters: backtracking can be expensive because it may explore many possibilities.

But it is still the right tool when the problem asks for all valid outcomes.

Interview checklist

When you see a recursion or backtracking problem, ask:

For recursion

• What is the smallest possible input?
• What answer can I return immediately?
• How do I shrink the problem?
• How do I combine smaller answers?

For backtracking

• What choices are available at each step?
• What state do I carry? Usually a path, index, or remaining amount.
• When is one full answer complete?
• What do I undo before trying the next branch?

Say this out loud

A strong interview explanation sounds like:

“I’ll define a recursive helper. The base case handles when we’ve finished making choices. At each step, I’ll try a choice, recurse, then undo it so other branches are independent.”

Next, we’ll move into Hashing and Hash Tables, where the main skill changes from exploring possibilities to finding and counting things quickly.