我们在设计算法的过程当中最常用的技术就是 reduction。
将问题 X 归纳为问题 Y 意味着我们为问题 X 设计的算法中以黑盒的形式使用了用来解决问题 Y 的算法来解决问题 X。而这个黑盒内部是如何工作的并不在我们的关心范围内。一般来说，我们最好将黑盒看作是一个能够通过魔法来正确解决问题 Y 的工具，不要试图理解它内部是如何工作的。
递归是一种非常强大的reduction，我们可以通过下面两个部分来简单地定义递归：
- If the given instance of the problem can be solved directly, solve it directly.
- Otherwise, reduce it to one or more simpler instances of the same problem.
我们可以想象有人会替我们完成 the simpler instances。 我们可以将这个帮我们解决 simpler instances 的人称为 Recursion Fairy，当然，这个递归精灵的学名是 Induction Hypothesis。
而所有递归算法都需要满足一个条件：There must be no infinite sequence of reductions to simpler and simpler instances.
递归算法的递归必须递归到能够通过其他方法求解的最基础的 base case，否则的话，递归算法就是无限循环。The most common way to satisfy this condition is to reduce to one or more smaller instances of the same problem. And solve the base case using some other methods.
归并排序和快速排序都遵守了一个 general three-step pattern called divide and conquer：
- Divide the given instance of the problem into several independent smaller instances of exactly the same problem.
- Delegate each smaller instance to the Recursion Fairy.
- Combine the solutions for the smaller instances into the final solution for the given instance.
If the size of any instance falls below some constant threshold, we abandon recursion and solve the problem directly, by brute force, in constance time.
There are three common cases where the level-by-level series (Σ) is especially easy to evaluate:
- Decreasing: If the series decays exponentially -- every term is a constant factor smaller than the previous term -- then T(n) = O(f(n)). In this case, the sum is dominated by the value at the root of the recursion tree.
- Equal: If all terms in the series are equal, we immediately have T(n) = O(f(n) * L) = O(f(n)logn).
- Increasing: If the series grows exponentially -- every term is a constant factor larger than the previous term -- then T(n) = O(nlogcr). In this case, the sum is dominated by the number of leaves in the recursion tree.