迭代者为人，递归者为神。——L. Peter Deutsch

一早起来，颇费周折地花了十几分钟，经过了几番失败的尝试，最终才找到了正确的思路。

 

如果A,B,C,D,E,F排成直线，那直接应用乘法原理即可: 4×3×3×3×3×3。但问题是现在是排成一周，这个答案不能保证最后的F和A不同色。

 

于是开始想，假如A初始选择了任意一种颜色，比如红色，那最后F是否与A同色的可能选择数量，与E的颜色选择有关。如果E与A同色，即是红色，那么F有三种选择，而如果E与A不同色，则F必须与A、E不同色，那只有两种选择。但然后呢，E是红色的涂色方法有多少种？E不是红色的涂色方法数呢？这两种情况也不好计算。

 

换一种角度，题目并未要求红、黄、蓝、绿都用上。满足条件，最少只需要用两种颜色，任选两种颜色，间隔染色即可。似乎按这种分类，把恰好用2种、3种、4种颜色染色的方法数都求出来，然后相加即可。但恰好用3种或4种颜色染色这一问题本身，也不好解。

 

至此，两种尝试都走不通。再回到一开始，4×3×3×3×3×3这个答案肯定比所求的要多，那么多出的是什么呢？如果能减去多出的数量，则也能得到正确的答案。我们知道，多出来的是F和A同色的情形，此时，A、B,  B、C,  C、D, D、E,  E、F仍不同色。如果把F和A这两个同色图形合并成一个，记为AF，则满足AF, B, C, D, E这五个图形相邻区域不同色！这，自然就联想到了递归。因为，这个问题的结构和原问题的结构一模一样。至此，该问题就迎刃而解了：如果把满足6个图形的颜色方法种数记为F(6), 那么F(6)= 4×3×3×3×3×3-F(5)，F(5)我们也不知道，但按照同样的方法类推，F(5)= 4×3×3×3×3-F(4)，最终初始条件F(2)=4×3是我们可以简单确定的。

 

我特别喜欢这种试错的过程，有时甚至感觉是一种享受。恰好，我最近也在给昍和几个小朋友讲简单递归。我一向鼓励孩子们从小的问题开始尝试。一开始找不到正确的途径很正常，能够认识到错误的尝试是错的本身也是一种非凡且不可或缺的能力。

 

递归中有个著名汉诺塔问题，是来自于源于印度的一个古老传说。传说在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

 

汉诺塔问题是一个经典递归问题，也是培养孩子递归思维的绝佳游戏。让孩子玩的时候，切莫告诉孩子攻略，而要给孩子充分的探索和思考空间。64片金片太多，可以让小朋友们从简单的开始。假设3根柱子是A, B, C。

1个盘片：需要移动1次

2个盘片：需要移动3次

3个盘片：需要移动7次

具体地，要把3个盘片从A号柱子搬到C号柱子，那么应该首先将上面两个1，2号盘片搬到B号柱子（移动3次），然后将最底下的3号盘片搬到C号柱子，然后再将1,2号盘片从B号柱子搬到C号柱子（移动3次）。

 

此时，实际上已经发现了相同结构的但规模更小的问题。也就是移动3个盘片，可以利用之前移动2个盘片的结果。

 

在此基础上，将N个盘片从A号柱移动到C号柱，我们不知道怎么做，但如果我们能首先把N-1个盘片从A号柱移动到B号柱，再把最底下的那个盘片从A号柱移动到C号柱，最后再把B号柱的N-1个盘片移动到C号柱，这个问题就解决了。在移动上面N-1个盘片的时候，由于底下的盘片最大，所以可以假设它并不存在。因此F(N)=2×F(N-1)+1。

 

按这一递推关系，这个序列是1，3，7，15，31，63，127， …。可以看出，N个盘片移动的次数是2^N-1。成功移动64个盘片需要18446744073709551615次。假如每移动一个盘片花1秒，并且这些僧侣能够正确无误地移动每一步的话（我是不相信的），需要花大约6000亿年才能完成

 

爬楼梯问题是另一个典型的递归问题：有10级楼梯，一次可以跨1级或2级，那么从下面爬到上面，一共有多少种不同的爬法。这个问题的关键是第一步怎么跨，如果跨1级楼梯，则还剩9级楼梯，如果跨2级楼梯，则还剩8级楼梯。因此10级楼梯的爬法是9级楼梯的爬法和8级楼梯爬法之和。想不到这个，没关系，可以从孩子先从1级、2级、3级楼梯开始尝试。具体，可以参考之前的一篇文章《神奇的斐波那契数列——大自然的数学密码》的分析。

 

总结一下，递归问题的要点：

•       要解决问题的规模较大

•       可以利用小规模问题的解来帮助解决更大规模问题

•       小规模问题的结构和原有问题的具有同样的结构（这一点最关键）

 

事实上，很多问题都可以用递归的思维来思考，包括最简单的乘法原理，它甚至能帮助我们理解乘法原理。例如，用1，2，3，4，5这5个数字可以组成多少个不同的5位数？这个问题同样可以从简单的开始尝试。

 

用1个数字可以构成多少个不同的1位数？答案显然是1

用2个数字可以构成多少个不同的2位数？答案显然是2

用3个数字可以构成多少个不同的3位数？答案是6。很多小朋友都会去枚举。但也可以不枚举。随便选一个数字作为第一位，有3种选法，剩下的2个数字可以构成2个两位数，因此总的方法数是3×2=6.

 

同样，5个数字组成多少个5位数我们不知道。但我们可以随便选择1个数字作为5位数的最高位，问题就转化为：剩下4个数字可以构成多少个四位数？如果我们知道了这个，那再此基础上乘以5就是希望得到的答案了。

 

我是学计算机的，对递归的重要性的认识再深刻不过了。递归在计算机中占有极为重要的地位，从形式化定义到算法，它的身影无处不在。可以这么说，对初涉编程的人，是否会用递归思维去解决问题是一名普通程序员迈向一名优秀程序员的一大门槛。从小让孩子具备一些递归思维，或许会让孩子在未来受益匪浅。