1.2.1 线性递归和迭代
我们从阶乘函数开始，这种函数的定义是：
n!=n·（n-1）·（n-2）…3·2·1
存在许多计算阶乘的方法，一种最简单的方法就是利用下面的认识，对任意正整数n，n!就等于n乘以（n-1）!：
n!=n·[（n-1）·（n-2）…3·2·1]=n·（n-1）！
这样，我们就能通过计算（n-1）!，再将其结果乘以n的方式计算n!。如果再注意到1!就是1，这些认识就可以直接翻译成一个计算机函数了：
我们可以利用1.1.5节介绍的代换模型，观察这个函数在计算6!时的行为，如图1.3所示。
现在我们从另一个不同的角度考虑阶乘计算。计算阶乘n!的规则可以改述为：首先乘起1和2，然后把结果乘以3，然后再乘以4，这样下去直至达到n。更形式化地说，我们维持一个变动的乘积product和一个从1到n的计数器counter，这个计算过程可以用counter和product的如下变化规则描述。在计算中的每一步，它们同时按下面的规则改变：
图1.3 计算6!的线性递归过程
可以看到，n!也就是计数器counter超过n时乘积product的值。
同样，我们又可以根据这个描述构造出一个计算阶乘的函数[26]：
与前面一样，我们也可以用代换模型查看6!的计算过程，如图1.4所示。
比较上面的两个计算过程。从一个角度看它们没什么不同：两者计算的是同一个定义域上的同一个数学函数，算出n!都需要使用与n成正比的步骤数。实际上，这两个计算过程甚至采用了同样的乘法运算序列，得到同样的部分乘积序列。但在另一方面，如果我们考虑这两个计算过程的“形状”，就可以看到它们的进展情况大相径庭。
图1.4 计算6!的线性迭代过程
考虑第一个计算过程，代换模型揭示出一种先逐步展开而后收缩的形状，如图1.3中的箭头所示。在展开阶段，该计算过程构造起一个推迟进行的运算形成的链条（在这里是一个乘法的链条），收缩阶段则表现为这些运算的实际执行。这种由推迟执行的操作链条刻画的计算过程，称为递归计算过程。为了执行这种计算过程，解释器需要维护好以后将要执行的那些操作的轨迹。在阶乘n!的计算中，推迟执行的乘法链条的长度就是记录其轨迹需要保存的信息量。这个长度随着n的值而线性增长（正比于n），与计算中的步骤数目一样。这种计算过程称为线性的递归计算过程。
与之相对，第二个计算过程里没有任何增长或收缩。对任意的n，在计算过程中的每一步，在我们需要保存的轨迹里，所有的东西就是名字product、counter和max_count的当前值。我们称这种过程为迭代计算过程。一般而言，迭代计算过程就是那种其中的状态可以用固定数目的状态变量描述的计算过程；而与此同时，又存在一套固定的规则，它们描述了该计算过程从一个状态到下一状态转换时这些变量的更新方法；还有一个（可能有的）结束检测，它说明了计算过程应该终止的条件。另外，在n!的计算中，所需计算步骤随着n线性增长，因此，这种过程称为线性的迭代计算过程。
我们还可以从另一个角度对比这两个计算过程。在迭代的情况里，在计算过程中的任何一点，上述的几个程序变量都提供了有关计算状态的一个完整描述。如果我们令这一计算在某两个步骤之间停下来，再想重新唤醒这一计算，只需要为解释器提供这三个变量的值。而对于递归计算过程，还存在一些额外的“隐含”信息，它们并没有保存在程序变量里，而是由解释器维持。这些信息表明了在所推迟的操作形成的链条里漫游的过程中“计算过程正处于何处”。这个链条越长，需要保存的信息也就越多[27]。
在比较迭代与递归时，我们必须当心，不要搞混了递归计算过程的概念和递归函数的概念。当我们说一个函数是递归的时，讨论的是一个语法形式上的事实，说明在这个函数的声明中（直接或间接地）引用了该函数本身。而在说某一计算过程具有某种模式时（例如，线性递归），我们说的是这一计算过程的进展方式，而不是相应函数书写上的语法形式。我们说某个递归函数（例如fact_iter）将产生迭代计算过程时，可能会有人感到不舒服。然而，这一计算过程确实是迭代的，因为其状态由它的三个状态变量完全刻画，在执行这一计算过程时，解释器只需要维持这三个名字的轨迹就足够了。
区分计算过程和函数可能使人感到困惑，一个原因来自各种常见语言（包括C、Java和Python）的情况。这些语言的大多数实现在解释任何递归函数时，消耗的存储量总是与函数调用的次数成正比，即使从原理上看该函数描述的计算过程是迭代的。作为这一事实的后果，要想在这些语言里描述迭代计算过程，就必须借助某些特殊的“循环结构”，如do、repeat、until、for和while等。我们将在第5章考察的JavaScript实现则没有这一缺陷，它总能在常量空间中执行迭代计算过程，即使这一计算是用一个递归函数描述的。具有这种特性的实现称为尾递归[28]。有了尾递归的实现，我们就可以采用常规的函数调用机制描述迭代，这也使得各种复杂的专用迭代结构变成不过是一些语法糖了[29]。
练习1.9 下面两个函数都是基于函数inc（它得到参数加1）和dec（它得到参数减1）声明的，它们各定义了一种得到两个正整数之和的方法。
请用代换模型描绘这两个函数在求值plus（4, 5）时产生的计算过程。这些计算过程是递归的或者迭代的吗？
练习1.10 下面的函数计算一个称为Ackermann函数的数学函数：
下面各语句的值是什么：
请考虑下面的函数，其中的A就是上面声明的函数：
请给出函数f、g和h对给定整数值n计算的函数的简洁数学定义。例如，k（n）计算5n2。