递归与分治策略是五大常见算法策略之一，分治策略的思想就是分而治之，即先将一个规模较大的大问题分解成若干个规模较小的小问题，再对这些小问题进行解决，得到的解，在将其组合起来得到最终的解。而分治与递归很多情况下都是一起结合使用的，能发挥出奇效（1+1>2），这篇文章我们将先从递归说起，再逐渐向分治过渡，主要讲解方式是通过9个例题来说明问题的，问题都是根据难度由简到难，由浅入深，对递归与分治能有个大概的了解雏形，当然最重要还是要做大量练习才能掌握。

0、递归   0.0、Fibonacci数列(易)   0.1、阶乘(易)   0.2、小青蛙跳台阶(易)   0.3、全排列问题(偏难)   0.4、整数划分(偏难) 1、分治策略   1.0、归并排序(一般)   1.1、二分查找(易)   1.2、棋盘覆盖(偏难)   1.3、日程表问题(偏难)

我们第一次接触递归一般都是在初学C语言时候的一道题目——Fibonacci数列中看到的，可能刚开始感觉有点不可思议，函数居然可以调用自己！Amazing！但事实如此，它确实存在，而递归也为我们某些算法的设计提供很大的便利，一般来说递归函数在理解起来并不是很难，甚至可以通过数学归纳法给予证明，但一直让人诟病的一点莫过于Debug的时候了，有时候调试一个较为复杂的递归函数能把人逼疯。

我们在这里将会由易到难，用一些例题先来讲解递归函数。采用Fibonacci数列来做这个引例来介绍递归函数。

  第一个数是1，第二个数也是1，从第三个数开始，后面每个数都等于前两个数之和。要求：输入一个n，输出第n个斐波那契数。 我们先来整理一下思路，分下面三步来看：

第一步，函数输入n，输出(也就是返回)第n个斐波那契数：

第二步，明确递归终止条件：

第三步，寻找函数的递归关系：

就这样，我们的一个斐波那契数列的递归函数就写完了。当然，这只是我们的一个开胃小菜，下面继续是入门级别的一个题，算阶乘。

输入一个数，输出它的阶乘。我们同样用那三步往下走。 第一步，函数输入n，返回n的阶乘

第二步，明确递归终止条件：

第三步，寻找函数的递归关系

做完前两个你肯定会觉得这不是很简单吗，不要急，我们要由易到难，由浅入深，这样阶梯式的科学学习。下面这个例子是小青蛙跳台阶问题，这个问题被用于递归和动态规划类问题的例题，我们这里先用递归解答，后面还会用动态规划策略来解决这个问题。

一只青蛙一次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上一个n级的台阶共有多少种跳法。 还是三步走，第一步，明确函数的输入及返回

第二步，明确递归终止条件 如果n=1，那小青蛙只能一次跳上第一节台阶，所以一种跳法，如果n=2，那小青蛙可以一次跳一节跳两次，或者直接一次跳两节，所以两种跳法。