一到周末就开始放荡自我，这不带着女朋友去万达电影院看电影（其实是由于整天呆在家敲代码硬是

被女朋友强行拖拽去看电影，作为一个有理想的程序员，我想各位应该都能体谅我），一到电影院，

女朋友说要买爆米花和可乐，我当时二话没说，臣本布衣躬耕于南阳，壤中羞涩，所以单买了爆米

花，买完都不带回头看老板的那种，饮料喝多了不好，出门的时候我带了白开水，还得亏我长得销

魂，乍一看就能看出是个社会精神小伙，女朋友也没多说什么，只是对我微了微笑（我估计是被我的

颜值以及独到的见解所折服），刚坐下没多久，女朋友突然问我，咱们现在坐在第几排啊？电影院里

面太黑了，看不清，没法数，这个时候，如果是你现在你怎么办？别忘了你我是程序员，这个可难不

倒我，递归就开始排上用场了。于是我就问前面一排的人他是第几排，你想只要在他的数字上加一，

就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前

问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告

诉你他在哪一排，于是你就知道答案了。这就是一个非常标准的递归求解问题的分解过程，去的过程

叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。我们用递推公式将

它表示出来就是这样的

f ( n ) = f (n - 1) + 1 其中，f ( 1 ) = 1

f(n)表示你想知道自己在哪一排，f(n-1)表示前面一排所在的排数，f(1)=1表示第一排的人知道自己在

第一排。有了这个递推公式，我们就可以很轻松地将它改为递归代码，如下：

int f(int n) {   if (n == 1) return 1;   return f(n-1) + 1; }

女朋友不懂递归，于是我给她讲递归需要满足的三个条件：

1.一个问题的解可以分解为几个子问题的解

何为子问题？子问题就是数据规模更小的问题。就好比，在电影院，你要知道，“自己在哪一排”的问

题，可以分解为“前一排的人在哪一排”这样一个子问题。

2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。

3.存在递归终止条件

把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需

要有终止条件。就好比，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是

f(1)=1，这就是递归的终止条件。

如何教女友敲递归代码？

刚刚铺垫了这么多，现在我们来看，如何来教女友敲递归代码？个人觉得，写递归代码最关键的是写

出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了。

你先记住这个理论。我举一个例子，带你一步一步实现一个递归代码，帮你理解。

假如这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法？如果有7个台阶，你可以2，2，2，1这样子上去，也可以1，2，1，1，2这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？

我们仔细想下，实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台

阶，另一类是第一步走了2个台阶。所以n个台阶的走法就等于先走1阶后，n-1个台阶的走法 加上先

走2阶后，n-2个台阶的走法。用公式表示就是：

f ( n ) = f (n - 1) + f ( n - 2 )

有了递推公式，递归代码基本上就完成了一半。我们再来看下终止条件。当有一个台阶时，我们不需

要再继续递归，就只有一种走法。所以f(1)=1。这个递归终止条件足够吗？我们可以用n=2，n=3这样

比较小的数试验一下。

n=2时，f(2)=f(1)+f(0)。如果递归终止条件只有一个f(1)=1，那f(2)就无法求解了。所以除了f(1)=1这一

个递归终止条件外，还要有f(0)=1，表示走0个台阶有一种走法，不过这样子看起来就不符合正常的

逻辑思维了。所以，我们可以把f(2)=2作为一种终止条件，表示走2个台阶，有两种走法，一步走完

或者分两步来走。

所以，递归终止条件就是f(1)=1，f(2)=2。这个时候，你可以再拿n=3，n=4来验证一下，这个终止条

件是否足够并且正确。

我们把递归终止条件和刚刚得到的递推公式放到一起就是这样的：

f(1) = 1; f(2) = 2; f(n) = f(n-1)+f(n-2)

有了这个公式，我们转化成递归代码就简单多了。最终的递归代码是这样的：