如何教会女友递归算法？

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

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

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

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

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

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

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

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

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

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

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

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

它表示出来就是这样的

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)

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

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

我总结一下，写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

如果以后再遇到类似问题，a可以分解为若干子问题b、c、d情况，你可以假设子问题b、c、d已经

解决，在此基础上思考如何解决问题a。而且，你只需要思考问题a与子问题b、c、d两层之间的关

系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递

归细节，这样子理解起来就简单多了。

因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调

用关系，不要试图用人脑去分解递归的每个步骤

。

如何教女友玩转汉罗塔

好了，讲完了递归算法，再回到电影院，不说别的，我还真那么做了，我真问了前面一排的人他是第

几排如果不清楚并让他跟我一样问他的上一排，显然，没循环到第三人，我差点被认为是神经病，差

点没被几个社会精神小伙打si，座位事情暂时告一段落，话说这电影属实够无聊，于是我不知是趁热

打铁，还是心血来潮，非要给女朋友玩一个汉罗塔游戏，我这暴脾气，刚实践递归算法被怼，是时候

挽回形象了，不秀一把递归算法我就不得劲。就是这个游戏，至于游戏规则，我觉得你体验一两把绝

对比我说的更加记忆深刻，，别看4399觉得有点弱zhi，再怎么说也承

载着童年 果然，女朋友是个哈皮，刚过第三关就扑街了，这个时候，头冒五丈光芒的我身披金甲挺身而出（貌

似有一点点小夸张，剧情需要嘛）一声不吭地敲了几行靓丽的代码

public class testhanoi {

	public static void main(string[] args) {
		hanoi(5,'a','b','c');  //可以理解为5个圈或者第5关
	}
	
	/**
	 * @param n 	共有n个圈
	 * @param a    开始的柱子
	 * @param b	中间的柱子
	 * @param c	目标的柱子
	 * 无论有多少个圈，都认为只有两个。上面的所有圈和最下面一个圈。
	 */
	public static void hanoi(int n,char a,char b,char c) {
		//只有一个圈。
		if(n==1) {
			system.out.println("第1个盘子从"+a+"移到"+c);
		//无论有多少个圈，都认为只有两个。上面的所有圈和最下面一个圈。
		}else {
			//移动上面所有的圈到中间位置
			hanoi(n-1,a,c,b);
			//移动下面的圈
			system.out.println("第"+n+"个圈从"+a+"移到"+c);
			//把上面的所有圈从中间位置移到目标位置
			hanoi(n-1,b,a,c);
		}
	}

}

只要main方法一致行，对着结果移动即可，就跟开了挂一样的，其实汉罗塔问题核心关键是无论有多少个圈，都认为只有两个。上面的所有圈和最下面一个圈。到这里，教女友敲递归算法代码，你学会了吗？

哦豁，明天还是一个晴天_{老天赐给宜春一个女朋友吧}毕竟我们程序员长得又帅敲代码又好看，是吧哥几个~~

如果本文对你有一点点帮助，那么请点个赞呗，谢谢~

最后，若有不足或者不正之处，欢迎指正批评，感激不尽！如果有疑问欢迎留言，绝对第一时间回复！

欢迎各位关注我的公众号，一起探讨技术，向往技术，追求技术，说好了来了就是盆友喔...