1.2.1 Linear Recursion and Iteration

We begin by considering the factorial function, defined by

我们从考察阶乘函数入手，它的定义如下：

n
!

=

n
⋅
(
n
−
1
)

⋅

(
n
−
2
)

⋯

3
⋅
2
⋅
1.

There are many ways to compute factorials. One way is to make use of the

observation that n

! is equal to n times (

n

−

1

)

! for any positive

integer n:

计算阶乘有许多种方式。一种方式是利用如下观察：对任意正整数 n，n

! 等于 n 乘以 (

n

−

1

)

!：

n
!

=

n
⋅
[
(
n
−
1
)

⋅

(
n
−
2
)

⋯

3
⋅
2
⋅
1
]

=

n
⋅
(
n
−
1
)
!
.

Thus, we can compute n

! by computing (

n

−

1

)

! and multiplying the

result by n. If we add the stipulation that 1! is equal to 1, this

observation translates directly into a procedure:

由此，我们可以通过先计算 (n − 1)! 再将结果乘以 n 来求得 n!。若再加上 1! 等于 1 这一约定，上述观察便可直接转化为如下过程：

We can use the substitution model of 1.1.5 to watch this

procedure in action computing 6!, as shown in Figure 1.3.

Figure 1.3: A linear recursive process for computing 6!.

我们可以借助 1.1.5 节的代换模型来观察这个过程计算 6! 的过程，如图 1.3 所示。图 1.3：计算 6! 的线性递归型计算过程。

Now let’s take a different perspective on computing factorials. We could

describe a rule for computing n

! by specifying that we first multiply 1 by

2, then multiply the result by 3, then by 4, and so on until we reach n.

More formally, we maintain a running product, together with a counter that

counts from 1 up to n. We can describe the computation by saying that the

counter and the product simultaneously change from one step to the next

according to the rule

现在让我们从另一个角度来看阶乘的计算。我们可以这样描述计算 n! 的规则：先用 1 乘以 2，再将结果乘以 3，然后乘以 4，如此继续直到乘到 n 为止。更形式化地说，我们维护一个累积乘积以及一个从 1 计数到 n 的计数器。计算过程可以描述为：计数器和乘积按照如下规则同步地从一步变化到下一步。

and stipulating that n

! is the value of the product when the counter

exceeds n.

并规定：当计数器超过 n 时，乘积的值就是 n! 的结果。

Once again, we can recast our description as a procedure for computing

factorials:

同样，我们可以将上述描述改写为一个计算阶乘的过程：

As before, we can use the substitution model to visualize the process of

computing 6!, as shown in Figure 1.4.

Figure 1.4: A linear iterative process for computing 6!.

与之前一样，我们可以用代换模型来展示计算 6! 的计算过程，如图 1.4 所示。图 1.4：计算 6! 的线性迭代型计算过程。

Compare the two processes. From one point of view, they seem hardly different

at all. Both compute the same mathematical function on the same domain, and

each requires a number of steps proportional to n to compute n

!.

Indeed, both processes even carry out the same sequence of multiplications,

obtaining the same sequence of partial products. On the other hand, when we

consider the “shapes” of the two processes, we find that they evolve quite

differently.

比较这两个计算过程。从某个角度看，它们几乎没有差别：两者都在同一个定义域上计算相同的数学函数，计算 n! 时各自所需的步骤数都与 n 成正比。事实上，两个计算过程甚至执行着完全相同的乘法序列，得到相同的中间乘积序列。然而，若我们审视这两个计算过程的“形态”，便会发现它们的演化方式大相径庭。

Consider the first process. The substitution model reveals a shape of

expansion followed by contraction, indicated by the arrow in Figure 1.3.

The expansion occurs as the process builds up a chain of

deferred operations

(in this case, a chain of multiplications). The contraction occurs

as the operations are actually performed. This type of process, characterized

by a chain of deferred operations, is called a

recursive process.

Carrying out this process requires that the interpreter keep track of the

operations to be performed later on. In the computation of n

!, the length

of the chain of deferred multiplications, and hence the amount of information

needed to keep track of it, grows linearly with n (is proportional to

n), just like the number of steps. Such a process is called a

考察第一个计算过程。代换模型揭示出一种先展开后收缩的形态，如图 1.3 中箭头所示。展开阶段是计算过程在积累一连串推迟执行的操作（此处为一连串乘法）；收缩阶段则是这些操作被实际执行的过程。这种以一连串推迟操作为特征的计算过程，称为递归型计算过程 (recursive process)。执行这种计算过程需要解释器记录那些稍后才需执行的操作。在计算 n! 时，推迟的乘法链的长度，以及追踪它所需的信息量，都随 n 线性增长（即与 n 成正比），与步骤数的增长方式相同。这样的计算过程称为

linear recursive process.

线性递归型计算过程。

By contrast, the second process does not grow and shrink. At each step, all we

need to keep track of, for any n, are the current values of the variables

product, counter, and max-count. We call this an

相比之下，第二个计算过程并不会增长和收缩。在每一步，无论 n 为何值，我们只需追踪变量 product、counter 和 max-count 的当前值。我们称这种计算过程为

iterative process. In general, an iterative process is one whose

state can be summarized by a fixed number of

state variables,

together with a fixed rule that describes how the state variables should be

updated as the process moves from state to state and an (optional) end test

that specifies conditions under which the process should terminate. In

computing n

!, the number of steps required grows linearly with n. Such

a process is called a

linear iterative process.

迭代型计算过程 (iterative process)。一般而言，迭代型计算过程是指其状态可以用固定数目的状态变量 (state variables) 来完整描述的计算过程，同时还有一条描述状态变量如何随计算过程从一个状态转移到下一个状态而更新的固定规则，以及一个（可选的）终止检测，用于规定过程应当在何种条件下停止。在计算 n! 时，所需步骤数随 n 线性增长。这样的计算过程称为线性迭代型计算过程。

The contrast between the two processes can be seen in another way. In the

iterative case, the program variables provide a complete description of the

state of the process at any point. If we stopped the computation between

steps, all we would need to do to resume the computation is to supply the

interpreter with the values of the three program variables. Not so with the

recursive process. In this case there is some additional “hidden”

information, maintained by the interpreter and not contained in the program

variables, which indicates “where the process is” in negotiating the chain of

deferred operations. The longer the chain, the more information must be

maintained.

这两种计算过程的区别还可以从另一个角度来看。在迭代的情形中，程序变量在任意时刻都完整地描述了计算过程的状态。若我们在两步之间暂停计算，要恢复计算只需向解释器提供这三个程序变量的值即可。而对于递归型计算过程则不然。此时存在一些“隐含的”额外信息，由解释器维护而非包含在程序变量中，它标记着计算过程在处理那一连串推迟操作时“走到了哪里”。链越长，需要维护的信息就越多。

In contrasting iteration and recursion, we must be careful not to confuse the

notion of a recursive

process with the notion of a recursive

在对比迭代与递归时，我们必须小心，不要混淆递归型计算过程 (recursive process) 与递归型

procedure. When we describe a procedure as recursive, we are

referring to the syntactic fact that the procedure definition refers (either

directly or indirectly) to the procedure itself. But when we describe a

process as following a pattern that is, say, linearly recursive, we are

speaking about how the process evolves, not about the syntax of how a procedure

is written. It may seem disturbing that we refer to a recursive procedure such

as fact-iter as generating an iterative process. However, the process

really is iterative: Its state is captured completely by its three state

variables, and an interpreter need keep track of only three variables in order

to execute the process.

过程 (recursive procedure) 这两个概念。当我们说一个过程是递归的，是指从语法上看这个过程的定义（直接或间接地）引用了其自身。但当我们说一个计算过程遵循线性递归这样的模式时，我们谈论的是计算过程如何演化，而非某个过程在语法上的写法。把 fact-iter 这样的递归型过程说成产生了迭代型计算过程，似乎令人费解，但这个计算过程确实是迭代的：其状态被三个状态变量完整捕获，解释器只需追踪这三个变量就能执行该计算过程。

One reason that the distinction between process and procedure may be confusing

is that most implementations of common languages (including Ada, Pascal, and C)

are designed in such a way that the interpretation of any recursive procedure

consumes an amount of memory that grows with the number of procedure calls,

even when the process described is, in principle, iterative. As a consequence,

these languages can describe iterative processes only by resorting to

special-purpose “looping constructs” such as do, repeat,

until, for, and while. The implementation of Scheme we

shall consider in Chapter 5 does not share this defect. It will execute

an iterative process in constant space, even if the iterative process is

described by a recursive procedure. An implementation with this property is

called

tail-recursive. With a tail-recursive implementation,

iteration can be expressed using the ordinary procedure call mechanism, so that

special iteration constructs are useful only as syntactic sugar.

过程与计算过程之间的区别之所以容易混淆，一个原因是大多数常见语言（包括 Ada、Pascal 和 C）的实现都被设计成：解释任何递归型过程都会消耗随过程调用次数增长的内存量，即便所描述的计算过程在本质上是迭代的也不例外。因此，这些语言只能借助专门的“循环构造”（如 do、repeat、until、for 和 while）来描述迭代型计算过程。我们将在第 5 章考察的 Scheme 实现不存在这一缺陷。它能在常量空间中执行迭代型计算过程，即便该迭代型计算过程是由递归型过程描述的。具有这种性质的实现称为尾递归 (tail-recursive)。借助尾递归实现，迭代可以用普通的过程调用机制来表达，因此专门的迭代构造仅作为语法糖而存在。