Skip to content

Recursion & Divide and Conquer

This page explains how recursion and divide and conquer differ and how they are used together.

Recursion

Definition

In mathematics and computer science, recursion is the use of a function in its own definition. In computer science it also refers to a method of solving a problem by repeatedly breaking it down into subproblems of the same kind.

Introduction

To understand recursion, you must first understand recursion.

The basic idea of recursion is that a function calls itself, directly or indirectly, so that solving the original problem turns into solving many subproblems of the same nature but smaller size. You only need to think about how to split the original problem into suitable subproblems, not about how each subproblem gets solved.

Here are some examples that help in understanding recursion:

  1. What is recursion?
  2. How do you sort a pile of numbers? Answer: split it in half, sort the left half, then the right half, and finally merge them. As for how to sort the left and right halves, please read this sentence again.
  3. How old are you this year? Answer: one year older than last year, and I was born in 1999.
  4. An example for understanding recursion

Recursion is very common in mathematics. For example, set theory formally defines the natural numbers as follows: 1 is a natural number, and every natural number has a successor, which is also a natural number.

Recursive code has two essential features: a base case and a call to itself. The self-call solves a subproblem; the base case defines the answer to the simplest subproblem.

1
2
3
4
int func(input value) {
  if (base case) return answer to the smallest subproblem;
  return func(smaller input);
}

Why write recursion

  1. The structure is clear and the code is easy to read. Compare, for example, these two implementations of merge sort:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // merge sort without recursion
    template <typename T>
    void merge_sort(vector<T>& a) {
      int n = a.size();
      for (int seg = 1; seg < n; seg = seg + seg)
        for (int start = 0; start < n - seg; start += seg + seg)
          merge(a, start, start + seg - 1, std::min(start + seg + seg - 1, n - 1));
    }
    
    // merge sort with recursion
    template <typename T>
    void merge_sort(vector<T>& a, int front, int end) {
      if (front >= end) return;
      int mid = front + (end - front) / 2;
      merge_sort(a, front, mid);
      merge_sort(a, mid + 1, end);
      merge(a, front, mid, end);
    }
    
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # merge sort without recursion
    def merge_sort_iterative(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 = start + seg + seg
            seg = seg + seg
    
    
    # merge sort with recursion
    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)
    

    In both listings, merge(a, front, mid, end) merges two sorted closed intervals of the same array, [front,mid] and [mid+1,end], in place.

  2. It trains you to analyze the structure of a problem. Once you have written enough recursion, you quickly notice when a problem breaks down into smaller problems of the same structure, and can then solve it efficiently.

Drawbacks of recursion

When a program runs, recursion is implemented with a stack. Every function call pushes a stack frame, and every return pops one. The stack is not infinitely large, so a recursion that goes too deep causes a stack overflow.

A recursive implementation may need extra space for the call stack, whereas an iterative one can get by with constant auxiliary space. For example, given the head of a linked list, compute its length:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// the typical iterative traversal
int size(Node *head) {
  int size = 0;
  for (Node *p = head; p != nullptr; p = p->next) size++;
  return size;
}

// recursive traversal, one node per level of recursion
int size_recursion(Node *head) {
  if (head == nullptr) return 0;
  return size_recursion(head->next) + 1;
}

Comparison of the two

Optimizing recursion

Main pages: search optimizations and memoization

A naive recursive implementation may recurse too many times and easily exceed the time limit. The recursion then has to be optimized.1

Divide and conquer

Definition

Divide and conquer does literally what its name says: it splits a complex problem into two or more identical or similar subproblems, and keeps splitting until the subproblems can be solved directly. The solution to the original problem is the combination of the solutions to the subproblems.

Procedure

The core idea of a divide-and-conquer algorithm is to divide and then conquer.

The process has roughly three steps: divide -> conquer -> combine.

  1. Divide the original problem into subproblems of the same structure.
  2. Keep dividing until you reach a base case that is easy to solve, and solve recursively.
  3. Combine the solutions to the subproblems into a solution to the original problem.

Problems that divide and conquer can solve usually have the following features:

  • The problem becomes easy to solve once its size is small enough.
  • The problem can be divided into several smaller instances of the same problem. In other words, it has optimal substructure: the solutions to the subproblems it is divided into can be combined into a solution to the problem itself.
  • The subproblems it is divided into are independent of one another: no two of them share a subproblem.
Note

If the subproblems are not independent, divide and conquer solves the shared subproblems over and over, which is a lot of unnecessary work. Divide and conquer still applies in that case, but dynamic programming is usually the better choice.

Take merge sort as an example. Suppose the function that implements it is called merge_sort. First state what the function is responsible for: sorting the array passed to it. This problem can clearly be divided: sorting an array amounts to sorting its left and right halves separately and then merging them into one array.

1
2
3
4
5
6
void merge_sort(an array) {
  if (it is easy to handle) return;
  merge_sort(left half of the array);
  merge_sort(right half of the array);
  merge(left half of the array, right half of the array);
}

Pass it half of the array, and when it is done that half is sorted. Notice how closely merge_sort resembles the template for a postorder traversal of a binary tree. That is because divide and conquer follows the pattern divide -> conquer (hit the bottom) -> combine (backtrack): first divide into left and right, then do the merging. Backtracking here is the stack unwinding, which is exactly a postorder traversal.

The merge function is implemented the same way as merging two sorted linked lists.

Key points

The key to writing recursion

Know what a function does and trust it to do that job. Never jump into the function to dig for more detail, or you will sink into endless detail and never get out. How many stack frames can a human brain push, after all?

Take binary tree traversal as an example.

1
2
3
4
5
void traverse(TreeNode* root) {
  if (root == nullptr) return;
  traverse(root->left);
  traverse(root->right);
}

These few lines are enough to traverse any binary tree. For the recursive function traverse(root), just trust that, given a root node root, it traverses the whole tree. All that remains is to pass the node's left and right children to the same function.

The same idea extends to an \(N\)-ary tree, and the code looks exactly the same. An \(N\)-ary tree, though, obviously has no inorder traversal.

1
2
3
4
void traverse(TreeNode* root) {
  if (root == nullptr) return;
  for (auto child : root->children) traverse(child);
}

Differences

Recursion versus enumeration

Recursion and enumeration differ as follows: enumeration splits a problem horizontally and then solves the subproblems one after another, whereas recursion breaks a problem down level by level, which is a vertical split.

Recursion versus divide and conquer

Recursion is a programming technique and a way of thinking about problems. Divide and conquer is an algorithmic idea that rests largely on recursion and addresses more specific problems.

Worked example

437. Path Sum III

You are given a binary tree in which every node stores an integer value.

Find the number of paths whose sum equals a given value.

A path does not have to start at the root or end at a leaf, but it must go downward (only from a parent to a child).

The tree has at most 1000 nodes, and the node values are integers in the range \([-10^6,10^6]\).

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

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

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
1
2
3
4
5
6
7
8
9
// divide-and-conquer_1.h
// definition of a binary tree node
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;

  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include "divide-and-conquer_2.h"

// Count the paths that start at node, extend downward, and have weights summing to sum.
int count(TreeNode *node, int sum) {
  if (node == nullptr) return 0;
  return (node->val == sum) + count(node->left, sum - node->val) +
         count(node->right, sum - node->val);
}

// Count separately the paths that start at the current node, those entirely in the left subtree, and those entirely in the right subtree.
int pathSum(TreeNode *root, int sum) {
  if (root == nullptr) return 0;
  return count(root, sum) + pathSum(root->left, sum) +
         pathSum(root->right, sum);
}
Analysis

The problem looks complicated, but the code is extremely short.

First, solving a tree problem recursively necessarily means traversing the whole tree, so the binary tree traversal skeleton (the function calling itself on the left and right subtrees) must appear in the main function pathSum. What should each node do, then? It should find out how many valid paths it and its subtrees contain. And that is the whole problem.

Following the advice above, we use this analysis to pin down what each recursive function should do:

The pathSum function: given a node and a target value, return the number of paths in the tree rooted at that node whose sum is the target value.

The count function: given a node and a target value, return the number of paths in the tree rooted at that node that start at that node and whose sum is the target value.

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include "divide-and-conquer_2.h"

// Count the paths that start at node, extend downward, and have weights summing to sum.
int count(TreeNode *node, int sum) {
  if (node == nullptr) return 0;
  return (node->val == sum) + count(node->left, sum - node->val) +
         count(node->right, sum - node->val);
}

// Count separately the paths that start at the current node, those entirely in the left subtree, and those entirely in the right subtree.
int pathSum(TreeNode *root, int sum) {
  if (root == nullptr) return 0;
  return count(root, sum) + pathSum(root->left, sum) +
         pathSum(root->right, sum);
}

Once again: know what each function can do, and trust it to do it.

To sum up, pathSum provides the binary tree traversal skeleton and calls count on every node during the traversal (a preorder traversal here, though an inorder or postorder traversal works just as well). count is itself a binary tree traversal, which looks for the paths that start at the given node and sum to the target value.

Practice problems

References and notes