【百科】递归——计算机思维和人的思维最大不同-新东方前途出国

递归——计算机思维和人的思维最大不同

 

人有人的思维，计算机有计算机的思维，它们很不相同。如果你要问其中最大的不同是什么，那就是一种被称为递归的逆向思维，它在英语里被称为recursive。相比之下，人的正向思维被称为递推（iterative）。对于计算机从业者来讲，想成为一个人才，在做计算机工作时就必须换一个思维方式，对普通人来讲这种思维方式也很有启发。  

要讲什么是递归，就要讲什么是递推。  

递推是人本能的正向思维，我们小时候学习数数，从1，2，3一直数到100，就是典型的递推。类似地，我们在学习过程中循序渐进，出发点都是这样正向，由易到难，由小到大，由局部到整体。  

比如我们在学习解方程时，先学习解一元方程，也就是说有一个未知数的方程，再学习解二元方程，也就是那些有两个未知数X，Y的方程，之后才学解三元方程，即有X，Y，Z的方程，最后推广到有任意未知数的方程，就是所谓的线性方程组。这种认识方法符合人的特点。类似地，我们在学习语文（和英语）时，先从组词开始，然后造简单的句子，然后再学习使用“因为...所以...”“既然...于是...”“既要...又要...”等连接词，造出复杂的句子。这种思维方式就是递推，它是正向的。  

如果用递推的方法计算一个整数的阶乘，比如5！＝1x2x3x4x5，那么做法是从小到大一个个乘起来。如果算100！，那么要从1乘到100。在生活中这种做法不仅合情合理，而且是天然而成的，我们从来不觉得它有什么问题。事实上，我们在中学里学的数学归纳法就是递推方法的典型应用。  

但是，对一些难题来讲，递推的方法会无计可施。比如下面一道智力题：“八皇后”问题。  

这个问题是19世纪的一位国际象棋棋手贝瑟尔提出的，讲的是在8×8格的国际象棋上摆放8个皇后，使其不会互相攻击，问有多少种摆法，怎么摆？  

我们知道在国际象棋中，皇后可以吃掉同一行、同一列和同一斜线上的棋子。因此，任意两个皇后都不能处于同一行、同一列或同一斜线上。  

这道题如果按照人的思维方式应该这样解：  

首先在第一行摆好一个棋子，它当然不会和任何棋子有冲突，然后再在第二行摆一个棋子，保证它和第一个棋子没有冲突，然后再摆第三行的，以此类推。  

下图给出了一种可能的解法。  

 

需要指出的是，在没有计算机之前找到所有可能的摆放非常困难，如果有兴趣的话可以在有空的时候做做这个游戏。如果能在5分钟内找到一个答案，就算是非常快的了。而找到它所有可能的摆法近乎不可能，大数学家高斯穷其一生只找到了76种方案。当然今天用计算机很快就能找到它的全部92种结果。

 

人之所以做不到穷举所有合理的摆放方法，倒不完全是因为它的排列组合非常多。事实上，“八皇后”问题所有可能的组合只有4万种，并不算多，更何况在这4万种排列中，大量的情况是一眼看上去就知道不合理的，可以马上排除。因此，即使一个智力中庸的人手工处理4万种情况，照说有几个月也该搞清楚了，更何况是数学天才高斯。高斯没有做出来并不是因为他水平不够，实际上当时很多的国际象棋选手们都在解这道题，找到的答案只有20多种，还不如高斯呢。这里面主要的原因是人类固有的递推思维方式，也就是从前到后，从小到大，并不适合解决这道题。  

那么计算机是怎么做的呢？它采用的是我们所说的递归方法。接下来我们就来介绍一下递归。为了简单起见，我们还是用前面阶乘那个简单的例子来说明递归。  

计算机是怎么计算阶乘的呢？它是倒着来的。比如要算5！，计算机就把它变成5x4！（五乘以四的阶乘）。当然，你会说，4！还不知道呢。没关系，计算机会说，采用同样的方法，把它变成4x3！。至于3！，则用同样的算法处理。最后做到1！时，计算机知道了它就等于自己，即1！＝1，从此不再往下扩展了。接下来，就是倒推回所有的结果，由于知道了1！，2！，然后3！，4！，5！就统统都知道了。  

从递归方法的过程，即从上向下层层展开，再从下到上一步步回溯，这和堆栈这种数据结构的一致性，即先进后出，后进先出。从上往下展开的次序是5，4，3，2，1，而从下往上回溯的次序则是1，2，3，4，5。当堆栈里的数字全部清空时，递归算法也就结束了。事实上在计算机内部，递归算法就是这么实现的。  

你可能会问，计算机为什么要这么算？答案是这样的算法逻辑非常简单。递归过程的每一步用的都是同一个算法，计算机只需要自顶向下不断重复而已。具体到阶乘的计算，无非就是某个数字N的阶乘，变成这个数乘以N－1的阶乘。因此，递归的本质有两条：其一是自顶而下，其二是自己不断重复。  

有了递归的方法，就能很容易解决“八皇后”问题了。具体的做法如下：

 

1. 假如棋盘上已经有了7个皇后，它们彼此的位置不冲突，那么在第八行从第1个位置到第8个位置一个一个地试验即可。当然，你会问前七个皇后怎么摆，才能保证它们彼此不冲突呢？答案很简单，按照第八步的方法照猫画虎地做。  

2. 当棋盘上一个棋子没有的时候，从第一行的第一个位置到第八个位置一个个分别试一试。  

当然，在上述过程中，有的摆放往后可以走得通，有些走不通。如果走不通，计算机会直接跳到下一个位置去试验。实际上在4万个摆法中，有92个是能走通的。4万个摆法对计算机来讲连一秒钟都不需要。  

从上述例子我们可以看出，人类的认识受到我们生活空间的局限，因此习惯于从小到大渐渐扩展的思维方式。而计算机因为可以直接处理大场景，因此有时会采用从大到小，层层分解的递归方法。这可以说给我们提供了一个新的看问题的方法和解决问题的思路。  

当然“八皇后”问题只是一个游戏，没有太多的实际意义。接下来，我们就来看一个具有意义的例子——自然语言处理中的语法分析。所谓语法分析，就是把一句话一级一级地分析出语法结构。比如分析这样一句话：  

今年北京颐和园的游客人数比往年减少了一成。  

我在前面讲了，人是从小的语法单元开始学习并且循序渐进的。也就是说要从字到词，从词到符合的词组（或者短语），再从词、词组构成句子的主、谓、宾。但在计算机分析语法结构时，则是自顶向下的，它的语法规则常常是这样写的：  

句子＝主语＋谓语部分  

主语＝定语＋名词短语  

定语＝名词短语 （或者形容词短语）  

名词短语＝形容词＋名词 （或者只有名词）  

谓语部分＝谓语＋宾语（或者谓语＋状语）  

等等，它们是从上往下嵌套的。  

用这样的语法分析上面的句子就很容易了，我们首先在“人数”两个字的后面划一道线，把它分为主语和谓语部分。然后在“游客”和“人数”两个词之间再划一道线，把主语分成定语和名词短语。这样做下去，一直分析到每一个词。不过，如果小学老师这样自顶向下教语文，再聪明的孩子也会糊涂的。  

因此，人循序渐进地学习是有道理的，但久而久之我们也就将自己局限在自底向上的工作方式中了，天生不适应自顶向下的做事方式。而计算机的思维在这方面则给了我们一个新的启发。  

总结一下内容：  

1. 很多时候，计算机的思维方式是自顶向下的，即递归。相比之下，人的思维方式是自底向上的递推。  

2. 递归的便利性来自于它本身是一个简单重复的过程。这样可以把一个复杂的问题分解成很多层简单的问题。  

3 很多时候我们需要逆向思维。  

【免责声明】

1、个别文章内容来源于网络善意转载，版权归原作者所有，如侵权，请联系删除；

2、所有图片来源于网络，版权归原作者所有。如有侵权问题请告知，我们会立即处理。