Recursion and Divide & Conquer – Breaking Problems to Solve Them Better

Sometimes the best way to solve a big problem… is to break it into smaller ones. That’s the core idea behind recursion and divide-and-conquer strategies. These are foundational techniques in programming and algorithm design.

We previously introduced recursion in CQH101, and we’ve put it into practice in our Train Tracks Solver. Now, let’s explore how these ideas power many of the world’s most famous algorithms.

What is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem.

Classic Example: Factorial

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Each call breaks the problem down: factorial(5) becomes 5 * factorial(4), and so on—until it hits the base case.

Key Ingredients

A base case that ends recursion.
A recursive step that moves closer to the base case.

What is Divide and Conquer?

Divide and Conquer is a strategy that:

Divides a problem into smaller sub-problems.
Conquers each sub-problem recursively.
Combines the results to get the final answer.

It’s a powerful pattern seen in algorithms like:

Merge Sort (split, sort, merge)
Quick Sort (partition and recurse)
Binary Search (search a half each time)

Example: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Each recursive call breaks the array down until it’s trivially sorted, then merges the sorted parts.

Why It’s Efficient

Recursion and divide & conquer can turn what seem like slow solutions into fast, elegant algorithms:

Binary search: O(log n)
Merge sort: O(n log n)
Quick sort: O(n log n) average

They work best when:

Problems can be divided evenly
Sub-problems are independent
You can combine results efficiently

Real-World Applications

Pathfinding (like our Train Tracks Solver) uses recursion to explore multiple paths.
Graphics – Fractal generation, recursive scene rendering
File systems – Recursively navigating nested folders

Even complex algorithms like Fast Fourier Transform (FFT) use divide & conquer to solve large mathematical problems quickly.

Performance and Pitfalls

Feature	Benefit	Risk
Elegant code	Clean, expressive logic	Can be harder to debug
Breaks big problems	Scales to large data sets	May hit recursion limits
Reusable logic	Solves any size input similarly	Stack overflows if unchecked

If a language doesn’t optimize tail-recursion, deep recursion can crash. That’s where techniques like memoization, iteration, or stack management come in.

What is Tail Recursion?

Tail recursion is a special kind of recursion where the recursive call is the very last thing a function does before returning its result.

Why it matters:

In many languages (especially functional ones), tail-recursive functions can be optimized to avoid growing the call stack—this is called tail call optimization (TCO). Instead of keeping each function call on the stack, the language reuses the current stack frame, making recursion as efficient as iteration.

Example – Tail Recursion vs Non-Tail Recursion

Not tail-recursive:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # multiplication happens *after* the recursive call

Tail-recursive:

def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)  # recursive call is the final action

In the second version, all the work (multiplication) is done before the recursive call, so it’s tail-recursive.

⚠️ Python does not optimize tail calls, but languages like Scheme, Haskell, and some versions of JavaScript do. Still, understanding tail recursion helps you write cleaner, stack-safe algorithms in the right contexts.

Challenge Time! 🔁

Write a recursive function to find the maximum number in a list.
Modify Merge Sort to count the number of comparisons it makes.
Try applying recursion to a problem you solved iteratively. Which is clearer?

Next up in CQH103: Dynamic Programming – where we’ll build on recursion and add memory to avoid solving the same sub-problems twice.