Recursion & Divide and Conquer

This page introduces the differences between recursion and divide-and-conquer algorithms and how to use them together.

Recursion

Definition

Recursion (English: Recursion) refers, in mathematics and computer science, to the method of using a function itself in the definition of a function; in computer science, it additionally refers to a method of solving a problem by repeatedly decomposing it into subproblems of the same kind.

Introduction

To understand recursion, you first have to understand what recursion is.

The basic idea of recursion is that a function calls itself directly or indirectly, thereby transforming the solution of the original problem into many subproblems with the same properties but smaller sizes. When solving the problem, you only need to focus on how to divide the original problem into subproblems that satisfy the conditions, without paying too much attention to how those subproblems are solved.

The following are some examples that help explain recursion:

1. What is recursion?
2. How do you sort a pile of numbers? Answer: split it in half, sort the left half and then the right half, and finally merge them; as for how to sort the left and right sides, please read this sentence again.
3. How old are you this year? Answer: last year's age plus one; I was born in 1999.

4. 

Recursion is very common in mathematics. For example, the formal definition of the 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 the termination condition and the self-call. The self-call solves the subproblem, while the termination condition defines the answer to the simplest subproblem.

int func(input_value) {
  if (base_case) return base_case_solution;
  return func(smaller_problem);
}

Why write recursion

1. The structure is clear and readability is high. For example, implement merge sort in different ways:

   === "C++" ```cpp // 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);
   }
   ```
   

   === "Python" ```python # 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)
   ```
   

   Clearly, the recursive version is easier to understand than the non-recursive version. The recursive version is self-explanatory: sort the left half, sort the right half, and finally merge the two halves. The non-recursive version looks incomprehensible, is full of difficult boundary-calculation details, is especially prone to bugs, and is difficult to debug.

2. Practice analyzing the structure of problems. When you discover that a problem can be decomposed into smaller problems with the same structure, writing recursion often makes you keenly notice this property, allowing you to solve the problem efficiently.

Disadvantages of recursion

During program execution, recursion is implemented using a stack. Every time a function call is entered, the stack gains one stack frame; every time a function returns, the stack loses one stack frame. However, the stack is not infinitely large, and too many recursive levels will cause stack overflow.

Clearly, recursive processing is efficient in some cases, such as merge sort; in some cases it is inefficient, such as counting the hairs on Sun Wukong's body, because the stack consumes extra space while simple iteration does not. For example, given the head of a linked list, calculate its length:

// 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 supreme
int size_recursion(Node *head) {
  if (head == nullptr) return 0;
  return size_recursion(head->next) + 1;
}

Optimizing recursion

Main pages: Search optimization and Memoized search

A relatively basic recursive implementation may make too many recursive calls and easily time out. In this case, recursion needs to be optimized.¹

Divide and conquer

Definition

Divide and conquer (English: Divide and Conquer), literally "divide and conquer", means dividing a complex problem into two or more identical or similar subproblems until the final subproblems can be solved directly and simply; the solution to the original problem is 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: divide -> solve -> combine.

1. Decompose the original problem into subproblems with the same structure.
2. After decomposing to a boundary that is easy to solve, solve recursively.
3. Combine the solutions to the subproblems into the solution to the original problem.

Problems solvable by divide and conquer generally have the following characteristics:

• The problem becomes easy to solve once its size is reduced to a certain extent.
• The problem can be decomposed into several smaller identical problems; that is, it has the optimal substructure property, and the solutions to the subproblems obtained by decomposing the problem can be combined into the solution to the problem.
• The subproblems into which the problem is decomposed are mutually independent; that is, the subproblems do not contain common subproblems.

Take merge sort as an example. Suppose the function implementing merge sort is named merge_sort. Clarify the responsibility of this function: sort the array passed to it. This problem can clearly be decomposed. Sorting an array is equivalent to sorting the left and right halves of that array separately and then merging them into one array.

void merge_sort(an_array) {
  if (easy_to_solve) return;
  merge_sort(left_half);
  merge_sort(right_half);
  merge(left_half, right_half);
}

Pass it half an array, and that half of the array will already be sorted after processing. Notice that merge_sort is extremely similar to the postorder traversal template for a binary tree. This is because the pattern of divide-and-conquer algorithms is decompose -> solve (reach the base case) -> combine (backtrack): first decompose left and right, then process the combination; backtracking means unwinding the stack, which is equivalent to postorder traversal.

The implementation of the merge function is the same as merging two sorted linked lists.

Key points

Key points for writing recursion

Understand what a function does and believe that it can complete the task; never jump into the function to investigate more details, or you will become trapped in endless details and unable to free yourself. How many stack frames can the human brain hold, anyway?

Take traversing a binary tree as an example.

void traverse(TreeNode* root) {
  if (root == nullptr) return;
  traverse(root->left);
  traverse(root->right);
}

These few lines of code are enough to traverse any binary tree. For the recursive function traverse(root), simply believe that when given a root node root, it can traverse this tree. Therefore, you only need to pass the node's left and right children to this function.

The same idea extends to traversing an N-ary tree. The code is exactly the same as for a binary tree. However, an N-ary tree clearly has no inorder traversal.

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 in sequence, while recursion decomposes the problem level by level in a vertical split.

Difference between recursion and divide and conquer

Recursion is a programming technique and a way of thinking about solving problems; divide and conquer is, to a large extent, based on recursion and is an algorithmic idea for solving more specific problems.

Detailed example

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

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

It returns 3. The paths whose sums equal 8 are:

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

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

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

int pathSum(TreeNode *root, int sum) {
  if (root == nullptr) return 0;
  int pathImLeading = count(root, sum);  // Number of paths starting at this node
  int leftPathSum = pathSum(root->left, sum);  // Total number of paths on the left (believe that it can calculate this)
  int rightPathSum =
      pathSum(root->right, sum);  // Total number of paths on the right (believe that it can calculate this)
  return leftPathSum + rightPathSum + pathImLeading;
}

int count(TreeNode *node, int sum) {
  if (node == nullptr) return 0;
  // Can it be a path by itself?
  int isMe = (node->val == sum) ? 1 : 0;
  // On the left, how many sum - node.val can you make?
  int leftNode = count(node->left, sum - node->val);
  // On the right, how many sum - node.val can you make?
  int rightNode = count(node->right, sum - node->val);
  return isMe + leftNode + rightNode;  // I can make this many
}

Exercises

• Recursion exercises on LeetCode
• LeetCode exercises focused on divide-and-conquer algorithms

References and notes