递归的人生哲学

当我们看书遇到看不懂的词句时候，我们会选择查字典，当查一个词，发现这个词的解释中某个词仍然不懂，于是我们开始查这第二个词。可是，第二个词的解释仍然有不懂的词，于是就查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，然后开始回退，逐个搞明白之前查过的每一个词的意思，最终，搞明白最开始的那个词的意思。

以上这样的场景相信大家肯定很熟悉，这个在计算机中就叫做“递归”，在《大辞海（信息科学券）》中对递归是这样定义的：在编程语言中，函数直接或间接调用函数本身的过程。该函数称“递归函数”。作为一种算法在程序设计语言中广泛应用。只需少量程序就可描述出解题过程所需要的多次重复计算，大大减少程序的代码量。

计算机和人的思维是相反的，人的正向思维被成为递推。什么是递推？递推是人本能的正向思维方式，我们学习数数，从 1，2，3 一直数到 100，就是典型的递推。类似地，我们在学习过程中，也都是正向的，从易到难，由小到大，由局部到整体。如果用递推的方法计算一个整数的阶乘，比如 5！=1×2×3×4×5，那么做法是从小到大一个个乘起来。如果是 100！，那么就从 1 乘到 100。这对我们来说不仅合情合理而且天然而成的。然而，计算机是怎么计算阶乘的呢？它是倒着来的。比如要算 5！，计算机就把它变成 5×4！（五成以四的阶乘）。你会说，4！还不知道呢。没关系，计算机会采用同样的方法，把它变成 4×3！。至于 3！，则用同样的算法处理。最后做到 1！时，计算机知道来它就等于自己，即 1！=1，从此不再往下扩展了。接下来，就是倒推回所有的结果，由于知道了 1！，2！，然后 3！，4！，5！就统统知道了。递归的方法的过程，即从上向下层层展开，再从下到上一步步回溯，如图堆栈数据结构一致，即先进后出，后进先出。从上往下展开的次序是 5，4，3，2，1，而从下往上回溯次序则是 1，2，3，4，5. 从此，我们可以了解到，递归过程的每一步用的都是同一个算法，计算机只需要自顶向下不断重复而已。具体倒阶乘的计算，无非就是某个数字 N 的阶乘，变成这个数乘以 N-1 的阶乘。因此，递归的本质有两条：其一是自顶向下，其二是自己不断重复。

递归需要满足的三个条件。

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

子问题就是数据规模更小的问题。比如，上面查字典的例子，你要查第一个词的问题，可以分解为“第二个词、第三个词的解释是什么”这样的子问题。

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

如查字典的例子，你查第一个词和查第二个、第三词其思路是一模一样的。

3. 存在递归终止条件。

依然是查字典的例子，你不能一直查下去，一点要存在你全部都理解的词，这个就是终止条件。

一个典型的递归面试题：

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

为了方便你理解，我们举一个实际的例子，当然加到 20 的时间太长，我们假设加到 10。假如我让你先选，你选了 2。接下来我选择加 2，这样我加到了 4，然后你选择加 1，你加到了 5，这时我还会选择加 2，就加到了 7。接下来，不论你选择加 1 到 8，还是加 2 到 9，我都能加到 10，因此我赢定了。当然，你可能觉得先作选择的人吃亏，那么这次我先来。我选择 1，你可能会选择加 2 到 3，然后我选择加 1 到 4。接下来，假如你选择加 2 到 6，我会选择加 1 到 7，这又回到第一次最后的状态了，我还是赢了。

可能你已经从上面的例子中想清楚这道题里面的技巧了，如果你还没有想清楚，我再等你五秒钟……好了，我们回来讲讲这道题。其实如果仅仅是抢 10，情况并不复杂，你即使想不清楚它的道理，试几次也能找到规律，但是如果是抢 20，情况就复杂多了。如果是抢 30，抢 50 呢？就不能通过穷举法这种笨办法解决问题了，就必须找它的规律了。

可能你已经看出来了。要想抢到 20，就需要抢到 17，因为抢到了 17，无论对方是加 1 还是加 2，你都可以加到 20。而要想抢到 17，就要抢到 14，以此类推，就必须抢到 11、8、5 和 2。因此对于这道题，只要第一个人抢到了 2，他就赢定了。这里面最核心的地方在于看清楚，无论对方选择 1 还是 2，你都可以让这一轮两个人加起来的数值等于 3，于是你就可以牢牢控制整个过程了。

那么这道看似是智力题的面试题是要考察候选人的什么技能呢？就是对计算机递归思想的理解。对于一般的人，让他们数数，数到 20。他们会从小往大数，但是这道题的解题思想正好相反。它是要寻找 20，就要先寻找 17，至于怎么从 17 到 20，方法你是知道的。接下来要寻找 17，就要寻找 14，等等，这就是递归的思想。

计算机科学和数学中的等价性原则，掌握来这个原则，就可以把很多问题归结为一类问题，解决了其中一个，其他的就迎刃而解。

递归就等同于我们生活中的倒逼，每年的 6 月 7 日-6 月 8 日是高考时间，学子们都会给自己倒计时，倒逼自己必须努力学习。倒逼是用意志力向自己的能力的底线不断发冲锋的过程。能用倒逼提升自己，注定是个自律、高自尊了不起的人。

参考吴军老师的《谷歌方法论》

王争老师的《数据结构与算法之美》