Skip to content

Recursion & Divide and Conquer

This page introduces the differences and combined applications of recursion and divide-and-conquer algorithms.

Recursion

Definition

Recursion (English: Recursion), in mathematics and computer science, refers to the method of using the function itself in its definition. In computer science, it additionally refers to a method of solving problems by repeatedly breaking them down into subproblems of the same type.

Introduction

To understand recursion, you must first understand what recursion is.

The basic idea of recursion is that a function calls itself directly or indirectly, so the solution to the original problem is transformed into many subproblems with the same properties but smaller scale. When solving, you only need to focus on how to divide the original problem into qualified subproblems, without paying too much attention to how each subproblem is solved.

Here are some examples to help understand recursion:

  1. What is recursion?
  2. How to sort a bunch of numbers? Answer: Divide into two halves, sort the left half first, then the right half, and finally merge them. As for how to sort the left and right halves, please reread this sentence.
  3. How old are you this year? Answer: Last year's age plus one year. I was born in 1999.
  4. An example to understand recursion

Recursion is very common in mathematics. For example, the formal definition of natural numbers in set theory is: 1 is a natural number, and every natural number has a successor, which is also a natural number.

The two most important features of recursive code are: termination condition and self-call. Self-call solves subproblems, while the termination condition defines the solution to the simplest subproblem.

1
2
3
4
int func(input value) {
  if (termination condition) return minimal subproblem solution;
  return func(reduced scale);
}

Why Write Recursion

  1. Clear structure and high readability. For example, implementing merge sort using different methods:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    // Merge sort algorithm 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 algorithm using 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
    # Merge sort algorithm without recursion
def merge_sort(a):
    n = len(a)
    seg, start = 1, 0
    while seg < n:
        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 algorithm using 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)

    Obviously, the recursive version is easier to understand than the non-recursive version. The recursive approach is clear: sort the left half, sort the right half, and finally merge the two halves. The non-recursive version seems obscure, filled with various hard-to-understand boundary calculation details, which are particularly prone to bugs and difficult to debug.

  2. Practice analyzing the structure of problems. When you discover that a problem can be decomposed into smaller problems of the same structure, writing recursion more often will help you keenly recognize this characteristic and solve problems efficiently.

Disadvantages of Recursion

During program execution, recursion is implemented using the stack. Each time a function call is entered, the stack adds a stack frame; each time a function returns, the stack removes a stack frame. Since the stack is not infinite, when the recursion depth is too high, it can cause stack overflow.

Obviously, sometimes recursion is efficient, such as in merge sort; sometimes it is inefficient, such as counting the hairs on Sun Wukong, because the stack consumes extra space, while simple iteration does not. For example, given a linked list head, calculate its length:

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

// I insist on writing recursion, recursion is the best
int size_recursion(Node *head) {
  if (head == nullptr) return 0;
  return size_recursion(head->next) + 1;
}

[Comparison of the two, compiler set to Clang 10.0, optimization set to O1](https://quick-bench.com/q/rZ7jWPmSdltparOO5ndLgmS9BVc)

Optimization of Recursion

Main page: Search Optimization and Memoization Search

More basic recursive implementations may have too many recursive calls, which can easily lead to timeouts. In such cases, recursion needs to be optimized.1

Divide and Conquer

Definition

Divide and Conquer (English: Divide and Conquer), literally means "divide and rule". It involves breaking down a complex problem into two or more similar or identical subproblems until the subproblems become simple enough to be solved directly. The solution to the original problem is then the combination of the solutions to the subproblems.

Process

The core idea of the divide-and-conquer algorithm is "divide and conquer".

The general process can be divided into three steps: decompose -> solve -> combine.

  1. Decompose the original problem into subproblems with the same structure.
  2. Recursively solve the subproblems until they reach a boundary that is easy to solve.
  3. Combine the solutions of the subproblems into the solution of the original problem.

Problems that can be solved by divide and conquer generally have the following characteristics:

  • The problem can be easily solved when its scale is reduced to a certain extent.
  • The problem can be decomposed into several smaller-scale identical problems, meaning the problem has optimal substructure. The solutions to the subproblems can be combined to form the solution to the original problem.
  • The subproblems decomposed from the problem are independent of each other, meaning the subproblems do not contain common subproblems.
Note

If the subproblems are not independent, the divide-and-conquer method will repeatedly solve common subproblems, resulting in unnecessary work. In such cases, although divide and conquer can still be used, dynamic programming is generally more appropriate.

Take merge sort as an example. Suppose the function implementing merge sort is named merge_sort. Clarify the responsibility of this function, which is to sort an incoming array. This problem can obviously be decomposed. Sorting an array is equivalent 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 (can be easily handled) 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 an array, and after processing, that half will be sorted. Note that merge_sort is extremely similar to the post-order traversal template of a binary tree. This is because the pattern of divide-and-conquer algorithms is decompose -> solve (bottom) -> combine (backtrack), first decomposing left and right, then handling the merge. Backtracking occurs when popping the stack, which corresponds to post-order traversal.

The implementation of the merge function is consistent with merging two sorted linked lists.

Key Points

Key Points for Writing Recursion

Understand the role of a function and trust that it can accomplish its task. Never jump into the function attempting to explore more details, otherwise you will fall into endless details and be unable to extricate yourself. How many stacks can the human brain handle?

Take traversing a binary tree 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 of code are sufficient to traverse any binary tree. For the recursive function traverse(root), just trust that given a root node root, it can traverse the tree. Therefore, you only need to pass the left and right nodes of this node to the function.

Similarly, extend this to traversing an N-ary tree. The writing is exactly the same as for a binary tree. However, for an N-ary tree, there is obviously no in-order traversal.

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

Differences

Difference Between Recursion and Enumeration

The difference between recursion and enumeration is that enumeration divides the problem horizontally and then solves the subproblems sequentially, while recursion decomposes the problem level by level, which is a vertical split.

Difference Between Recursion and Divide and Conquer

Recursion is a programming technique, a way of thinking to solve problems; divide-and-conquer algorithms are largely based on recursion and are algorithmic ideas for solving more specific problems.

Example Explanation

437. Path Sum III

Given a binary tree, each node stores an integer value.

Find the total number of paths where the sum of the node values equals a given value.

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

The binary tree has no more than 1000 nodes, and the node values are integers in the range [-1000000,1000000].

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 with sum equal 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
#include "divide-and-conquer_1.h"

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);
}

int pathSum(TreeNode *root, int sum) {
  if (root == nullptr) return 0;
  return count(root, sum) + pathSum(root->left, sum) +
         pathSum(root->right, sum);
}
Problem Analysis

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

First, understand that recursively solving tree problems necessarily requires traversing the entire tree, so the binary tree traversal framework (recursively calling the function itself on the left and right subtrees) must appear in the main function pathSum. So what should each node do? They should check how many eligible paths they and their subtrees contain. Well, that's the end of this problem.

Following the previously mentioned technique, clearly define what each recursive function should do based on the above analysis:

PathSum function: Given a node and a target value, return the total number of paths in the tree rooted at this node that sum to the target value.

count function: Given a node and a target value, return the number of paths in the tree rooted at this node that start with this node and sum to the target value.

Reference Code (with comments) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int pathSum(TreeNode *root, int sum) {
  if (root == nullptr) return 0;
  int pathImLeading = count(root, sum);  // number of paths starting with itself
  int leftPathSum = pathSum(root->left, sum);  // total paths on the left (trust it can compute)
  int rightPathSum =
      pathSum(root->right, sum);  // total paths on the right (trust it can compute)
  return leftPathSum + rightPathSum + pathImLeading;
}

int count(TreeNode *node, int sum) {
  if (node == nullptr) return 0;
  // Can it be a separate path?
  int isMe = (node->val == sum) ? 1 : 0;
  // Left side, how many can you make that sum to sum - node.val?
  int leftNode = count(node->left, sum - node->val);
  // Right side, how many can you make that sum to sum - node.val?
  int rightNode = count(node->right, sum - node->val);
  return isMe + leftNode + rightNode;  // This is how many I can make
}

Again, understand what each function can do and trust that they can accomplish it.

To summarize, the PathSum function provides the binary tree traversal framework, calling the count function for each node during traversal (pre-order traversal is used here, but in-order and post-order traversal would also work). The count function is also a binary tree traversal, used to find paths starting from that node that sum to the target value.

Exercises

References and Notes

  1. labuladong's algorithm cheat sheet - Detailed explanation of recursion ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用