在上一篇文章中，我们已经学习了算法时间复杂度的基本知识。现在我们开始进入真正的算法的介绍——分治策略(divide-and-conquer strategy)。

分治策略是一种普遍的算法思想，拆开来看，“分”是分开，“治”是治理，“分治”就是“分而治之"，把一个问题分成几个小问题求解。分治策略主要包含三个步骤：

①分解：将问题划分成若干个子问题，这些子问题与原问题形式一样，只是规模更小

②解决：求解子问题

③合并：由子问题的解得到原问题的解

既然子问题和原问题是同一种形式的，那么如果对于原问题可以用分治策略进行求解，那么子问题应该就也可以应用同样的策略。 这样，求解原问题需要求解子问题，求解子问题又需要求解子子问题，求解子子问题又需要求解子子子问题。这种调用自身不停地向下求解的过程就叫做递归(recursion)。递归其实有很多例子。不知道大家有没有见过投屏时大屏套小屏的场景: 这就是一种递归。录屏软件想要捕获显示器的内容并由窗口显示出来，但是显示器内容又包括自身的窗口，这就造成了录屏软件想要捕获显示器，就必须捕获自身窗口和除了自身窗口以外的内容，而自身窗口又需要捕获显示器，也就是我们说的“无限套娃”。理论上，这种递归是无限的，而事实上，系统为了防止它无限调用把系统资源占尽搞崩，所以设置了一个尽头。 按照这个原理，我们用C语言也可以写出一个无限递归的函数：

结果为

而我们不想要无限递归，因为这无法解决我们的问题。我们想要递归有一个尽头，这个尽头叫做递归的边界条件。例如上面那个函数func()，想要让它能够自己停下来，可以变成：

Java的Collections类提供了binarySearch方法。事实上C与C++也有二分查找库函数bsearch。通过二分查找的例子，我们可以发现递归的过程是： 实际上，不使用递归也可以完成这个过程。