Recursion and Divide & Conquer Algorithms

This article explains the differences between recursion and divide & conquer, and how they can be combined. We’ll define each concept, discuss when and why to use them, and provide clear code examples.

Recursion

Definition

Recursion is a method in mathematics and computer science where a function calls itself directly or indirectly. In computer programming, it is a problem-solving strategy in which a problem is broken down into similar but smaller subproblems, and a function calls itself to solve these subproblems.

An Introduction to Recursion

To really understand recursion, it helps to grasp that a function can call itself. So, solving a large problem often boils down to solving several smaller instances of the same problem. The key is to consider only how to break a problem into simpler subproblems, without worrying too much about the internal details of each subproblem.

Consider these everyday examples:

Explaining what recursion is often involves using recursion itself.
Sorting a list of numbers by splitting them into two halves: sort the left half, then the right half, and finally merge the sorted halves.
Calculating one’s age: your age today is simply your age last year plus one.
In mathematics, natural numbers are defined recursively: 1 is a natural number, and each natural number has a unique successor that is also a natural number.

A recursive solution always has two important parts:

A termination condition (base case) that stops the recursion.
A recursive call that handles a smaller subproblem.

A typical recursive structure looks like this:

def func(value):
    if termination_condition:
        return smallest_solution
    return func(smaller_value)

Advantages of Recursion

Clear Structure and Readability
Recursion often leads to code that is easier to understand. For example, consider merge sort. Here’s a non-recursive version versus a recursive version.

# Non-recursive merge sort
def merge_sort(a):
    n = len(a)
    seg = 1
    while seg < n:
        start = 0
        while start < n - seg:
            merge(a, start, start + seg - 1, min(start + seg + seg - 1, n - 1))
            start += seg + seg
        seg += seg

# Recursive merge sort
def merge_sort(a, front, end):
    if front >= end:
        return
    mid = front + (end - front) // 2
    merge_sort(a, front, mid)
    merge_sort(a, mid + 1, end)
    merge(a, front, mid, end)

The recursive version is more intuitive: sort the left half, sort the right half, then merge the two halves. In contrast, the iterative version is cluttered with loop and boundary conditions, which can lead to difficult-to-debug errors.

Helping You Understand Problem Structure
Recursion trains you to recognize when a complex problem can be broken down into similar, smaller problems. With practice, you’ll start to notice these patterns and solve problems more efficiently.

Drawbacks of Recursion

Recursion uses the call stack to manage function calls. Every time a function recurses, a new frame is added to the stack, and when the function returns, the frame is removed. The call stack has limited space, so deep recursion can lead to a stack overflow.

Sometimes recursion is very efficient (like in merge sort), but other times it consumes extra space unnecessarily compared to simple iterative methods. For example, consider computing the length of a linked list:

# Simple iterative approach
def size(head):
    count = 0
    p = head
    while p is not None:
        count += 1
        p = p.next
    return count
 
# Recursive approach (demonstrating recursion, but not optimal for this problem)
def size_recursion(head):
    if head is None:
        return 0
    return size_recursion(head.next) + 1

Optimizing Recursion

Basic recursive implementations might lead to too many recursive calls, potentially causing timeouts or excessive use of resources. In such cases, optimization strategies like search optimizations or memoization can improve efficiency.

Divide & Conquer

Definition

Divide & conquer is a strategy that involves breaking a complex problem into two or more smaller, similar subproblems, solving the subproblems directly when they become simple enough, and then combining those solutions to solve the original problem.

Process

The main idea of divide & conquer is "divide the problem, solve the subproblems, and merge the results." This process includes three steps:

Divide the problem into smaller subproblems that have the same structure.
Conquer (solve) the simple subproblems using recursion.
Combine the solutions to form the solution to the original problem.

Problems suitable for divide & conquer share common attributes:

When the problem size is reduced to a small enough level, it can be easily solved.
The problem can be divided into smaller independent problems (optimal substructure) whose solutions can be combined.
The subproblems do not share any overlapping portions. If they do, solving the same subproblem repeatedly can lead to inefficiencies—in such cases, dynamic programming might be a better approach.

Take merge sort as an example. The goal of the merge_sort function is to sort an array. It divides the array into two halves, recursively sorts each half, and then merges the sorted halves.

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)

The merging function typically resembles the process of merging two sorted lists.

Key Points for Writing Recursive Functions

Believe in the responsibility of each function and trust that it can perform its task without unnecessary scrutiny. In other words, define what each function should do and avoid diving into its inner workings repeatedly.

Take, for instance, the traversal of a binary tree:

def traverse(root):
    if root is None:
        return
    traverse(root.left)
    traverse(root.right)

This function efficiently traverses any binary tree by recursively visiting the left and right branches. When dealing with an N-ary tree, the concept remains similar:

def traverse(root):
    if root is None:
        return
    for child in root.children:
        traverse(child)

Differences Between Concepts

Recursion vs. Enumeration

While enumeration breaks a problem into multiple pieces and then processes them one by one (horizontally), recursion breaks a problem down level by level (vertically).

Recursion vs. Divide & Conquer

Recursion is a general programming technique—a mindset of breaking down a problem and solving it using self-similarity. Divide & conquer is a specific algorithmic strategy that often uses recursion to solve particular problems efficiently.

Detailed Example: Path Sum III

Consider the following problem:

Given a binary tree where each node stores an integer value, count the number of paths that sum to a given value. The path does not need to start at the root or end at a leaf, but it must go downward (i.e., from parent to child).

For example:

Given the binary tree below and target sum 8:

10 /
5 -3 / \
3 2 11 / \
3 -2 1

There are three paths that sum to 8:

5 -> 3
5 -> 2 -> 1
-3 -> 11

Code Explanation

The solution uses recursion. The core idea is that any problem involving trees requires a complete traversal. For each node, the algorithm checks how many valid paths exist that start from that node and then recursively does the same for its children.

We define two recursive functions:

The first function handles the overall traversal of the tree. For every node, it computes the number of valid paths starting at that node and combines these counts with the counts from its left and right subtrees.
The second function counts all paths starting from a given node that add up to the target sum.

Below is the Python implementation:

def pathSum(root, target):
    if root is None:
        return 0
    # Count paths that start from the root, plus paths in left and right subtrees
    path_including_root = count(root, target)
    left_paths = pathSum(root.left, target)
    right_paths = pathSum(root.right, target)
    return path_including_root + left_paths + right_paths
 
def count(node, remaining):
    if node is None:
        return 0
    # Check if the current node's value completes the sum
    is_path = 1 if node.val == remaining else 0
    # Recursively count valid paths from left and right children
    left_count = count(node.left, remaining - node.val)
    right_count = count(node.right, remaining - node.val)
    return is_path + left_count + right_count

Always remember: trust in the responsibility of each function. In the pathSum function, you simply believe that count can correctly compute the number of valid paths starting from a node, and vice versa.

Exercises

Practice solving recursion problems on platforms that focus on recursive techniques.
Work on various divide & conquer problems to build a stronger intuition for breaking down complex problems.

This guide is designed to provide beginners with a clear and accessible introduction to recursion and divide & conquer. With regular practice and deeper exploration, these concepts will become invaluable tools in your problem-solving arsenal.

Prefix Sum and Difference Arrays Simulation