用递归代替循环

假设工作中的你，需要写一个倒数程序。该程序接收一个数字，例如10，然后显示从10到0的数字。现在先暂停一下，选择一门编程语言来实现这个程序，做完以后，再往下阅读。或许你用了JavaScript，并且写了如下循环。

这样写没什么问题，只是你可能没想到循环以外的做法。那还能怎么做呢？试试换成递归吧。以下是初级版的递归countdown。

让我们一步步来分析。

第1步：调用countdown(10)，因此参数number为10。

第2步：将number（值为10）打印到控制台。

第3步：countdown函数在结束前，调用了countdown(9)（因为number -1等于9）​。

第4步：countdown(9)被执行，会将number（值为9）打印到控制台。

第5步：countdown(9)结束前，调用了countdown(8)。

第6步：countdown(8)被执行，会将number（值为8）打印到控制台。

在继续步骤分解之前，先回顾下该递归是怎样实现我们的需求的。countdown里并没有任何循环结构，它通过调用自身就能够从10开始倒数并将每个数字打印出来。

几乎所有循环都能够转换成递归。但能用不代表该用。递归的强项在于巧妙地解决问题，但在上面的例子中，它并不比普通的循环更加优雅、高效。我们很快就会看到能让递归发挥威力的场景，但在那之前，还是先理清递归的运作方式。

基准情形

让我们把countdown函数继续下去。为了简洁一点，我们跳过一些步骤。

第21步：调用countdown(0)。

第22步：将number（值为0）打印到控制台。

第23步：调用countdown(-1)。

第24步：将number（值为-1）打印到控制台。你也看到了，这种写法不够完善，这样下去我们就会不断地打印负数。

要解决这个问题，得在数到0时就停住，以免递归一直往下数。

我们可以加个条件判断，来保证当number为0时，不再调用countdown()。

这样，当number为0时，我们的代码就不会再去调用countdown()，而是直接返回。

在递归领域（真有这么一个地方）​，不再递归的情形称为基准情形。对于刚才的countdown()函数来说，0就是基准情形。

阅读递归代码

递归是需要时间和练习才能适应的，到那时候，你会掌握两种技巧：阅读递归代码和编写递归代码。阅读递归代码相对简单一点，所以就先从这里入手吧。我们会以阶乘作为例子。阶乘的演示如下所示。3的阶乘是：

5的阶乘是：

以此类推。以下Ruby代码会以递归计算的方式返回一个数的阶乘。

此代码初看可能会让人有点困惑，可以按照以下流程来读。

(1) 找出基准情形。

(2) 看该函数在基准情形下会做什么。

(3) 看该函数在到达基准情形的前一步会做什么。

(4) 就这样往前推，看每一步都在做什么。

让我们将此流程应用到刚才的代码上。稍作分析，就可以看出里面有两条路径。

第二条路的factorial有调用自身，是递归发生的地方。

第一条路并没有调用自身，因此这里是基准情形。

于是，number为1时，是基准情形。接着，想象factorial方法在基准情形下，即factorial(1)的处理流程。其相关代码如下。

好，这很简单，因为是基准情形，所以没有递归。调用factorial(1)就会直接返回1。于是找来一张纸，记下该结果。

然后，回到上一步的factorial(2)，相关代码如下。

调用factorial(2)就会返回2 * factorial(1)。要计算2 * factorial(1)，就得先知道factorial(1)的结果。要是检查下前面所记，你会发现那是1。因此，2 * factorial(1)就是2 * 1，即是2。把这个也记到纸上。

那么，factorial(3)又会是什么呢？再回看代码。

代入参数便是3 * factorial(2)。那么factorial(2)是什么呢？你不用从头计算，因为它的结果已经写在纸上了，是2。于是factorial(3)会返回6（3 * 2=6）​。将结果记下，然后继续。

现在请自行计算factorial(4)。如你所见，这种从基准情形入手再往上分析的思路，对理解递归代码是多么有益。