转载

递归，上帝的思维方式

To iterate is human, to recurse, divine.

人理解迭代，神理解递归。

最近编写一个项目测试脚本，需要使用深度优先搜索算法，该算法又涉及对递归的理解，然后我就深深的陷进去了。

人的思维，一般是迭代 (iteration)。比如人都是先学习加减法，再学习乘除法，最后学习微积分。数学归纳法其实就是一种迭代，从一个简单的起点，推广到一般情况。

递归 (recursion)，则是一种反人类的逆向思维。作为一个程序员，每次使用递归时，代码总是简洁到让自己心虚，因为这种思维逻辑甚至是反常识的。

先说一个简单的例子，阶乘。计算5!，迭代的思维一般是按照1x2x3x4x5的顺序计算。而递归的思维则是5! = 5x4!，那么4!是什么呢？不重要，因为4! = 4x3!。这样一直往前推，直到1! = 1。这个时候再把每个值往回代入计算，就能得到最终的结果。

递归，上帝的思维方式

程序实现上简洁到了极致：

def Factorial(n):

assert n > 0, "n > 0"

if n == 1:

return 1

return n * Factorial(n - 1)

再说一个复杂一点的例子，斐波那契数列。1,1,2,3,5,8,13……。这个数列从第3个数字开始，每个数字都等于前两个数字相加。问题是第100个数字是什么？迭代的思维一般是一个一个往后加，直到找到第100个。而递归的思维是，第100个数字等于第99个数字加第98个数字，而第99个数字等于第98个数字加第97个数字，递归下去，最终只要知道第1个数字和第2个数字的值，就可以回溯回去，第100个数字的值也就知道了。

递归，上帝的思维方式

程序简洁的让人心疼：

def Fibonacci(n):

assert n > 0, "n > 0"

if (n == 1) or (n == 2):

return 1

return Fibonacci(n - 1) + Fibonacci(n - 2)

运用递归思维解决问题，需要注意以下几点：

问题本身可以拆分成更为简单的子问题，而子问题可以通过同样的方法解决。
问题需要有边界，否则会掉进递归死循环。
递归并不高效，大数量级的问题要慎用，你可能永远等不到答案。

一旦你理解了递归，很多问题就会变得很傻瓜。有一个有趣的智力题，八皇后问题：

在8×8格的国际象棋棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

下面是一种可能的摆法：

递归，上帝的思维方式

高斯穷其一生只找到76种摆法，而事实上有92种摆法。高斯的数学水平毋庸置疑，但是他也不得不被人类递推或者说迭代的思维影响。大家不防用递归的思维方式去寻找一种摆法。关于八皇后问题的详细分析请参考前一篇文章《八皇后问题》，也可以后台回复『 八皇后 』查看。

递归思维有什么用？递归的思维，仅仅用来玩智力游戏岂不是太没有意义了。

其实计算机的设计，很多时候就是自顶而下的。应用程序运行的堆栈设计，也是天然满足递归的。

大到社会组织架构，如省、市、县、乡的行政划分，小到公司组织，如集团、子公司、部门、团队的划分，其实也是一种递归。每一层都是上一层的缩小版，每一层也只关心它的下一层，好的组织架构应该是不提倡越级管理的。

人生也可以用递归的思维去思考。很多时候不要总是考虑多年后做成什么，而是多年以后的自己，希望今天的自己活成什么样子？也许，你就不会拼了命的赚钱，也不会刻意的勤俭节约。一生的长度，倒推当下，我们可能就会放弃很多不必要的追求，学会人生做减法的哲学。

递归思维是自顶而下的，我们做事的时候可以先从整体上考虑。先明确需要达到的大目标，而不是一开始就在细节上较真，这其实也是系统论的思想。很多初入职的程序员，在没有清楚项目整体功能架构的情况下，就急于写代码，最终往往导致多次返工，事倍功半。

当然，递归也有个陷阱。如果没有一个边界限制，那就会掉进递归死循环。

很多人每次决心学习英语，就开始背单词，坚持不了多久可能就放弃了。再想起学英语时，又重新开始背单词。其实不防反过来，有了英语基础的人，不必纠结于词汇量，而是可以根据自己的兴趣爱好，直接阅读Wikipedia的词条，遇到不认识的单词，先借助上下文猜测词意，必要时再查阅词典。这样英语水平才会有质的提升。

父母一辈忙忙碌碌，很多时候把梦想转嫁到孩子身上，孩子离开学校，要不了多久又把梦想转嫁到他们的孩子身上，比如给孩子报各种兴趣班。这样就变成从前有座山，山上有个庙，庙里有个老和尚给小和尚讲故事…无穷尽也。想要跳出递归死循环，就必须努力去完成自己的梦想，而孩子应该有他们自己的梦想。

I must study politics and war, that our sons may have liberty to study mathematics and philosophy. Our sons ought to study mathematics and philosophy, geography, natural history and naval architecture, navigation, commerce and agriculture in order to give their children a right to study painting, poetry, music, architecture, statuary, tapestry and porcelain.

约翰·亚当斯说，我必须研究政治和战争，那么我的儿子们也许才会拥有研究数学和哲学、地理学、自然史、军舰建造、航海术、商业和农业的自由，以便给他们的孩子们研究绘画、诗歌、音乐、建筑、雕塑、织艺和陶瓷的权利。

最后，友情提醒，不要试图短时间内理解递归，其结果要么是理解错了，要么会很痛苦。