凡治众如治寡，分数是也。
解决规模庞大的问题的有效方法之一，就是将其分解为若干规模更小的子问题，再通过递归机制分别求解。这种分解持续进行，直到子问题规模缩减至平凡情况。这也就是所谓的分而治之（divide-and-conquer）策略。
与减而治之策略一样，这样也要求对原问题重新表述，以保证子问题与原问题在接口形式上的一致。由于将问题分解为若干个子问题，故每一递归实例都可能做多次递归，故称作多路递归（multi-way recursion）。通常会将问题一分为二，故称作二分递归（binary recursion）。
需要强调的是，无论是分解为两个还是更大常数个子问题，对算法总体渐进复杂度并无实质影响。
案例1：数组求和之二分版本
算法思路：
以居中的元素将数组一分为二，递归地对子数组分别求和，最后子数组之和相加即为原数组总和。
算法实现：
int sum(int *A, int lo, int hi)
{
if(lo == hi)
return A[lo];
int mi = (lo + hi) >> 1;
return sum(A, lo, mi) + sum(A, mi + 1, hi);
}
算法分析：
- 时间复杂度：
与线性递归版本一样，此处每一递归实例中的非递归计算都只需要常数时间，递归实例共计2n - 1个。故二分版本时间复杂度为O(n)，与线性递归版本相同。 - 空间复杂度：
到达递归基时，此时占用的空间最大（因为之后便会递归返回数据，并退栈）。因此任一时刻的活跃递归实例总数都不会超过logn + 1。鉴于每个递归实例仅需常数空间，故算法空间复杂度为O(logn)，相对线性递归版本的O(n)，有了很大改进。
但并非所有问题都适宜采用分治策略！实际上除了递归，此类算法的计算消耗主要来自两个方面。首先是子问题划分，即把原问题分解为形式相同、规模更小的多个子问题，比如数组求和二分版本将数组分为前、后两段。其次是子解答合并，即由递归所得子问题的解，得到原问题整体的解，比如由子数组之和累加得到整个数组之和。
为使分治策略真正有效，不仅必须保证以上两方面的计算都能高效地实现，还必须保证子问题之间相互独立（各个子问题可独立求解，而无需借助其它子问题的原始数据或中间结果。）。否则，或者子问题之间必须传递数据，或者子问题之间需要相互调用，无论如何都会导致时间和空间复杂度的无谓增加。以下就以Fibonacci数列的计算为例说明这一点。
案例2：Fibonacci数
fib(n) = n < 2 ? n : fib(n - 1) + fib (n - 2)
1、Fibonacci数之二分递归
算法实现：
int fib(int n)
{
if(n <= 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
算法分析：
二分递归版本的子问题f(n - 1) 与 fib(n - 2) 实际上并非彼此独立。
- 时间复杂度：
二分版本的时间复杂度高达O(2^n)，究其原因在于，计算过程中所出现的递归实例的重复度极高。 - 空间复杂度：
O(logn)
