谷歌与递归

感性认识递归

在讲解“递归”这个抽象概念之前，让我们来重温一下昔日往事。小时候，当我们在缠着长辈讲故事时，长辈们可能就用下面的故事来“忽悠”我们：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事！故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚正在给小和尚讲故事！故事是什么呢……

除非讲故事的人自己停下来不讲了，不然这个故事可以“无限”讲下去，原因就是“故事”嵌套的“故事”就是“故事”本身，这就是语言上“递归”的例子。

但是，由于这个故事并没有一个终止的条件，因此，它实际上是陷入了一种有头无尾的死循环，因此并不符合程序设计领域中定义的“递归”。在程序设计领域，递归是指函数（或方法）直接或间接调用自身的一种操作，如下图所示。递归调用的好处在于，它能够大大减少代码量，将原本复杂的问题简化成一个简单的基础操作来完成。在编写程序的过程中，“递归调用”是一个非常实用的技巧。

递归示意图

从上图中可以看出，函数不论是直接调用自身，还是间接调用自身，都是一种无终止的过程。

在程序设计中，显然不能出现这种无终止的调用。因此，在编写递归算法时，读者要特别注意，所有递归一定要有终止条件，这又被称作递归出口。如果一个递归函数缺少递归出口，执行时就会陷入死循环。递归出口通常可用if语句来设置，在满足某种条件时不再继续，调用某个值，结束递归。

谷歌公司有世界上最聪明的程序员。他们不光聪明，还很有自己的“冷幽默”，别出心裁。比如说，假设你不懂得什么是“递归”，不妨去谷歌搜索一下这个关键词。然后你会发现，除了给出必要的搜索结果，谷歌还给出了一条提示语“您是不是要找：递归”，如下图所示。

谷歌程序员的“冷幽默”

乍一看，你可能会觉得，这谷歌搜索是不是有问题啊？我的确、明明、丝毫无误地查询的就是“递归”，还提示什么啊？其实，这正是谷歌搜索引擎背后程序员们的“冷幽默”所在：如果你点击了那个提示“递归”，搜索引擎将再次搜索“递归”——相当于自己调用自己——这不正是递归的精髓吗？

或许你懂了，会心一笑，但可能还会疑惑：这也不对啊，所有的递归都有终止条件，如果我们一直点击这个提示词“递归”，查询岂不是会无限循环下去？

放心，你一定不会一直点击下去。因为这个递归的出口正是，查询的人终于懂得什么是递归而不再查询。而你就是那个懂得的人。

递推思维与递归思维

递归（recurse）在计算机领域被广泛应用，它不仅是一种计算方法，更是一种思维方式。科技作家吴军博士认为：递归思维是人与计算机思维最大的差别之一。著名计算机科学家彼得·多伊奇（L. Peter Deutsch）甚至认为，To iterate is human, torecurse divine（迭代是人，递归是神）。

对于计算机从业者来说，想成为顶级人才，在做计算机相关工作时，必须具有递归思维。对于普通人来讲，这种思维方式也很有启发。因此，不论从哪个角度，递归思维都值得我们培养和掌握。

人的常规思维被称为递推（iterate）思维。在中文里，“递推”和“递归”只有一字之差，但在英文世界里，它们的差别可大了去了，可谓“差之毫厘，谬以千里”。

我们先来说说递推。比如小时候我们学习数数，从1、2、3一直数到100，就是典型的递推。类似地，我们在学习过程中循序渐进，如水到而渠成，出发点都是正向的，由易到难，由小到大，由局部到整体。

递推是人类本能的正向思维，于我们而言，可谓熟稔于心。而“递归”则有一定的反常识。

下面我们以计算一个整数的阶乘为例来说明两种思维的差别。如果用人类常用递推方式计算一个整数的阶乘，比如5！＝1×2×3×4×5，那么做法是从小到大一个数一个数接连相乘。如果计算10的阶乘（10！），过程也是类似的，即从1乘到10。在生活中，这种做法不仅合情合理，而且浑然天成。事实上，在中学里学的数学归纳法（利用当n成立时的结论，推导n+1）就是递推方法。

为了简单起见，我们还是用前面求阶乘的简单例子来说明递归的原理。计算机是怎么计算阶乘的呢？它是倒着来的。比如要算5！，计算机就把它变成5×4！（即5乘以4的阶乘）。当然，我们可能会质疑，4！还不知道呢！但没有关系，计算机会采用同样的方法，把4！变成4×3！。至于3！，则用同样的算法处理。最后做到1！时，计算机知道1！＝1（这就是递归的终止条件），自此便不再往下扩展了。

接下来，就是倒推回所有的结果。因为知道了1！，顺水推舟，就知道了2！，然后可知3！、4！和5！。从上面描述的递归过程可以看出，递归的方法论可归结为两步：先从上向下层层展开，再从下到上一步步回溯。

递归调用的函数

你可能会问，计算机为何要这么算？这么算有何优势？答案并不复杂，利用递归可以使算法的逻辑变得非常简单。因为递归过程的每一步用的都是同一个算法，计算机只需要自顶向下不断重复即可。

具体到阶乘的计算，无非就是某个数字n的阶乘，变成这个数乘以n-1的阶乘。因此，递归的法则就两条：一是自顶而下（从目标直接出发），二是不断重复。

递归的另一个特点在于，它只关心自己下一层的细节，而并不关心更下层的细节。你可以理解为，递归的简单源自它只关注“当下”，把握“小趋势”，虽然每一步都简单，但一直追寻下去，也能获得自己独特的精彩。

下面我们就以计算阶乘为例，分别使用递推和递归方式实现，大家可体会二者的区别。

【范例】利用递推和递归方式分别计算n！

01   #用正向递推的方式计算阶乘

02   def iterative_fact( n): 
03       fact = 1
04       for i in range(1, n +1):
05           fact *= i
06       return fact
07    
08   #用逆向递归的方式计算阶乘
09   def recursive_fact( n ):
10       if n <= 1 :
11           return n;
12      return n * recursive_fact(n - 1)
13     
14   #调用递推方法计算
15   num = 5
16   result= iterative_fact( num );
17   print("递推方法：{}!= {}".format(num, result))
18   #调用递归方法计算
19   result= recursive_fact(num)
20   print("递归方法：{}!= {}".format(num, result)) 

【运行结果】

递推方法：5!= 120

递归方法：5!= 120

递归函数的优点在于，定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但正向递推（即循环）的逻辑不如逆向递归的逻辑清晰。

谷歌公司的递归面试题

有这么一个游戏：有两个人，第一个人先从1和2中挑一个数字，第二个人可以在对方的基础上选择加1或者加2，然后又轮到第一个人，他也可以选择加1或者加2，之后再把选择权交给对方，就这样双方交替地选择加1或者加2，谁先加到20，谁就赢了。对于这个游戏，你用什么策略保证一定能赢？

【案例分析 1】

如果用正向的递推思维（比如说穷举法），并不容易想清楚，而且还容易漏掉合理的解。但如果用逆向的递归思维，问题的解就非常容易推导出来。我们先从结果出发，如果要想抢到20，就需要抢到17，因为抢到了17，无论对方是加1还是加2，你都可以加到20。而要想抢到17，就要抢到14，以此类推，就必须抢到11、8、5和2。

因此对于这道题，只要第一个人抢到了2，他就赢定了。这是因为，无论对方选择加1还是加2，他都可以让这一轮两个人加起来的数值等于5。同样的道理，在当前和为5的基础上，无论对方选择加1或加2，他都能让和向着8进发。以此类推，整个过程都被他牢牢控制，最终的数列之和，毫无悬念地被他锁定在20。

当然谷歌的面试题并非这么简单，如果你答对第一道题，那么紧接着就会有下一道题。

按照上述方法，在不考虑谁输谁赢的情况下，从开始（以1或2为起点）加到20，有多少种不同的递加过程？比如1，4，7，10，12，15，18，20算一种；2，5，8，11，14，17，20又是一种。那么一共会有多少种这样的过程呢？

【案例分析 2】

这道题显然并不简单，通过正向的穷举法很难完备遍历。解这道题的技巧还是要使用递归。我们假定数到20有F(20)种不同的路径，那么到达20这个数字，前一步只有两个可能的情况，即从18直接跳到20，或者从19数到20。

由于从18跳到20和从19到20是不同的，因此达到20的路径数量，其实就是达到18的路径数量，加上达到19的路径数量，也就是说，F(20)＝F(18)＋F(19)。类似地，F(19)＝F(18)＋F(17)。这就是递推公式。

最后，F(1)只有一个可能，就是1，F(2)有两个可能，要么直接跳到2，要么从1达到2。知道了F(1)=1和F(2)=2，就可以知道F(3)。知道F(3)，就可以知道F(4)，因为F(4)= F(3)+ F(2)，以此类推，一直到F(20)即可。

聪慧如你，你一定看出来了，这就是著名的斐波那契数列，如果我们认为F(0)也等于1，那么这个数列就长成这样：1(F(0))，1，2，3，5，8，13，21，……这个数列几乎按照几何级数的速度增长，到了F(20)，就已经是10946了。因此，仅仅靠正向的穷举法，基本上是不可能把所有情况都列举出来的。

上述面试题来自曾就职于谷歌公司的吴军博士。吴军博士在分析这道面试题时指出，在数学和计算机上，等价性原则是一个非常重要的原则。很多问题的表象看起来纷繁复杂，但抽丝剥茧之后，其本质是等价的。比如说，如果一个楼梯有20阶，你每次可以爬一阶歇一会，也可以爬两阶歇一会，爬到20阶一共有多少种歇息法？这个问题的解，其实和“谁先抢到20”是一样的，也是一个斐波那契数列。

从某种程度上来看，递归思维是一种以结果为导向，反向追寻，直到追寻到原点（递归的终止条件）的思维方式，一旦原点问题得以解决，其后的问题都会迎刃而解。