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:
- What is recursion?
- 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.
- How old are you this year? Answer: one year older than last year, and I was born in 1999.

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 | |
Why write recursion
-
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. -
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 | |
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.
- Divide the original problem into subproblems of the same structure.
- Keep dividing until you reach a base case that is easy to solve, and solve recursively.
- 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 | |
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 | |
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 | |
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 | |
1 2 3 4 5 6 7 8 9 | |
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
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 | |
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
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: fudonglai, AngelKitty, labuladong, Ir1d, cbw2007, 24OI-bot, abc1763613206, Lutra-Fs, wongsyrone, invalid-email-address, algofighter, sshwy, Enter-tainer, NachtgeistW, houbaron, StudyingFather, Konano, leoleoasd, melxy1997, iamtwz, Xeonacid, Alisahhh, ksyx, zirnc, Menci, shawlleyw, TrickEye, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.