Rekursion und Backtracking

Recursion Fundamentals

A recursive function calls itself with a smaller version of the problem until it hits a base case that stops the chain.

Every recursion needs two things:

1. Base case - the simplest input where you return directly.
2. Recursive case - break the problem down and call yourself.

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

The Call Stack - Visualised

Each recursive call pushes a frame onto the call stack. When the base case returns, frames pop in reverse order.

factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1) → returns 1
    ← returns 2
  ← returns 6
← returns 24

If there's no base case, the stack overflows. Python's default recursion limit is 1,000 frames.

Fibonacci - The Classic Trap

The naïve recursive Fibonacci is O(2ⁿ) because it recomputes the same sub-problems. Memoisation fixes this in O(n) time and space.

from functools import lru_cache

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

Backtracking - Try Everything, Then Undo

Backtracking is recursion with a twist: you make a choice, recurse, then undo the choice before trying the next option. Think of it as exploring a maze - walk forward, hit a dead end, walk back, try the next path.

The Backtracking Template

def backtrack(state, choices):
    if is_solution(state):
        result.append(state.copy())
        return
    for choice in choices:
        if is_valid(choice):
            state.add(choice)       # choose
            backtrack(state, ...)   # explore
            state.remove(choice)    # un-choose

This three-step pattern - choose, explore, un-choose - is the backbone of nearly every backtracking problem.

Permutations

Generate all orderings of [1, 2, 3]. At each level, pick an unused number, recurse, then un-pick.

         []
      /   |   \
    [1]  [2]  [3]
    / \   ...
 [1,2] [1,3]
   |      |
[1,2,3] [1,3,2]  ... (6 total)

There are n! permutations, so the time complexity is O(n × n!).

Combinations and Subsets

Combinations (n choose k): at each element, include it or skip it, but only recurse forward to avoid duplicates.

Subsets: same idea without a size constraint - every node in the recursion tree is a valid subset. There are 2ⁿ subsets.

N-Queens - Walkthrough

Place N queens on an N×N board so none attack each other. For N=4:

. Q . .
. . . Q
Q . . .
. . Q .

Strategy: place one queen per row. For each row, try every column. Check column, main diagonal, and anti-diagonal conflicts. If safe, place and recurse to the next row. If stuck, backtrack.

Track conflicts with three sets: cols, diag (row − col), and anti_diag (row + col).

Sudoku Solver - Concept

Find an empty cell, try digits 1–9. For each digit, check row, column, and 3×3 box constraints. If valid, place and recurse. If no digit works, undo and backtrack. The pruning from constraints makes it tractable despite the huge search space.

Word Search in a Grid

Given a 2D board of letters and a target word, start from every cell and DFS in four directions, matching one character at a time. Mark cells as visited during recursion and unmark on backtrack to allow other paths.

Time Complexity of Backtracking

The cost depends on the branching factor (choices per step) and depth (steps to a solution). For b branches and d depth: O(bᵈ).

| Problem | Branching | Depth | Complexity | |---------|-----------|-------|------------| | Permutations | n, n−1, … | n | O(n!) | | Subsets | 2 | n | O(2ⁿ) | | N-Queens | ~n | n | O(n!) worst case |

Pruning to Optimise

Pruning means skipping branches you know will fail. Examples:

• N-Queens: skip columns already occupied.
• Sudoku: skip digits that violate constraints.
• Combination sum: skip if remaining sum < 0.

Good pruning can turn an impractical search into a fast one.

📚 Further Reading

• NeetCode - Backtracking playlist - curated problems with video walkthroughs
• Tech Interview Handbook - Recursion - patterns and common pitfalls
• LeetCode Backtracking study plan - progressive problem set