5.1.4 Using a Stack to Implement Recursion

With the ideas illustrated so far, we can implement any iterative process by

specifying a register machine that has a register corresponding to each state

variable of the process. The machine repeatedly executes a controller loop,

changing the contents of the registers, until some termination condition is

satisfied. At each point in the controller sequence, the state of the machine

(representing the state of the iterative process) is completely determined by

the contents of the registers (the values of the state variables).

借助前面介绍的思想，我们可以实现任意迭代型计算过程：只需设计一台寄存器机器，使其拥有与计算过程中每个状态变量对应的寄存器。该机器反复执行一个控制器循环，不断改变各寄存器的内容，直到满足某个终止条件为止。在控制器序列的每一步，机器的状态（即迭代型计算过程的状态）完全由各寄存器的内容（即各状态变量的值）所决定。

Implementing recursive processes, however, requires an additional mechanism.

Consider the following recursive method for computing factorials, which we

first examined in 1.2.1:

然而，实现递归型计算过程还需要一种额外的机制。请看下面这个计算阶乘的递归方法，我们在 1.2.1 节中最早讨论过它：

As we see from the procedure, computing n

! requires computing (

n

−

1

)

!.

Our GCD machine, modeled on the procedure

从这个过程可以看出，计算 n! 需要先计算 (n−1)!。我们的 GCD 机器是按照如下过程建模的：

similarly had to compute another GCD. But there is an important

difference between the gcd procedure, which reduces the original

computation to a new GCD computation, and factorial, which

requires computing another factorial as a subproblem. In GCD, the

answer to the new GCD computation is the answer to the original

problem. To compute the next GCD, we simply place the new arguments

in the input registers of the GCD machine and reuse the machine’s

data paths by executing the same controller sequence. When the machine is

finished solving the final GCD problem, it has completed the entire

computation.

同样地，它也需要计算另一个 GCD。但 gcd 过程与 factorial 过程之间存在一个重要的区别：gcd 将原始计算归约为一个新的 GCD 计算，而 factorial 则需要将另一个阶乘计算作为子问题来求解。在 GCD 中，新 GCD 计算的答案就是原问题的答案。为了计算下一个 GCD，我们只需将新的参数放入 GCD 机器的输入寄存器，并通过执行同一条控制器序列来复用该机器的数据通路。当机器解决完最后一个 GCD 问题时，整个计算也随之完成。

In the case of factorial (or any recursive process) the answer to the new

factorial subproblem is not the answer to the original problem. The value

obtained for (

n

−

1

)

! must be multiplied by n to get the final answer.

If we try to imitate the GCD design, and solve the factorial

subproblem by decrementing the n register and rerunning the factorial

machine, we will no longer have available the old value of n by which to

multiply the result. We thus need a second factorial machine to work on the

subproblem. This second factorial computation itself has a factorial

subproblem, which requires a third factorial machine, and so on. Since each

factorial machine contains another factorial machine within it, the total

machine contains an infinite nest of similar machines and hence cannot be

constructed from a fixed, finite number of parts.

对于阶乘（或任何递归型计算过程）而言，新的阶乘子问题的答案并不等于原问题的答案。必须将 (n−1)! 的结果乘以 n，才能得到最终答案。如果我们试图模仿 GCD 的设计，通过递减寄存器 n 并重新运行阶乘机器来求解阶乘子问题，那么在将结果乘以 n 时，n 的旧值便已无从获取。因此我们需要第二台阶乘机器来处理该子问题。而这台第二阶乘机器本身又含有一个阶乘子问题，需要第三台阶乘机器，如此递推下去。由于每台阶乘机器内部都包含另一台阶乘机器，整台机器就形成了无限嵌套的同类机器，因此无法用固定的有限数量的部件构造出来。

Nevertheless, we can implement the factorial process as a register machine if

we can arrange to use the same components for each nested instance of the

machine. Specifically, the machine that computes n

! should use the same

components to work on the subproblem of computing (

n

−

1

)

!, on the

subproblem for (

n

−

2

)

!, and so on. This is plausible because, although

the factorial process dictates that an unbounded number of copies of the same

machine are needed to perform a computation, only one of these copies needs to

be active at any given time. When the machine encounters a recursive

subproblem, it can suspend work on the main problem, reuse the same physical

parts to work on the subproblem, then continue the suspended computation.

尽管如此，只要我们能够安排让机器的每个嵌套实例复用同一组部件，就可以将阶乘计算过程实现为一台寄存器机器。具体而言，计算 n! 的机器应当使用同一组部件来处理计算 (n−1)! 的子问题、计算 (n−2)! 的子问题，依此类推。这是合理的，因为尽管阶乘计算过程在理论上需要无限多份相同机器的副本才能完成计算，但在任意时刻只有其中一份需要处于活动状态。当机器遇到一个递归子问题时，它可以暂停主问题的工作，复用同一批物理部件来处理子问题，然后再继续被暂停的计算。

In the subproblem, the contents of the registers will be different than they

were in the main problem. (In this case the n register is decremented.)

In order to be able to continue the suspended computation, the machine must

save the contents of any registers that will be needed after the subproblem is

solved so that these can be restored to continue the suspended computation. In

the case of factorial, we will save the old value of n, to be restored

when we are finished computing the factorial of the decremented n

register.

在处理子问题时，各寄存器的内容与主问题中的不同。（在本例中，寄存器 n 被递减了。）为了能够继续被暂停的计算，机器必须保存在子问题解决后仍然需要用到的寄存器内容，以便在恢复被暂停的计算时将它们还原。在阶乘的情形下，我们将保存 n 的旧值，待递减后的寄存器 n 的阶乘计算完成后再予以恢复。

Since there is no a priori limit on the depth of nested recursive calls,

we may need to save an arbitrary number of register values. These values must

be restored in the reverse of the order in which they were saved, since in a

nest of recursions the last subproblem to be entered is the first to be

finished. This dictates the use of a

stack, or “last in, first

out” data structure, to save register values. We can extend the

register-machine language to include a stack by adding two kinds of

instructions: Values are placed on the stack using a save instruction

and restored from the stack using a restore instruction. After a

sequence of values has been saved on the stack, a sequence of

restores will retrieve these values in reverse order.

由于嵌套递归调用的深度没有先验上限，我们可能需要保存任意数量的寄存器值。这些值必须按保存时的逆序进行恢复，因为在递归嵌套中，最后进入的子问题最先完成。这就要求使用一种栈 (stack)，即“后进先出”的数据结构，来保存寄存器值。我们可以通过增加两种指令来扩展寄存器机器语言，使其支持栈：使用 save 指令将值压入栈，使用 restore 指令从栈中弹出值。将一组值依次压入栈之后，一系列 restore 操作将按逆序取回这些值。

With the aid of the stack, we can reuse a single copy of the factorial

machine’s data paths for each factorial subproblem. There is a similar design

issue in reusing the controller sequence that operates the data paths. To

reexecute the factorial computation, the controller cannot simply loop back to

the beginning, as with an iterative process, because after solving the

(

n

−

1

)

! subproblem the machine must still multiply the result by n. The

controller must suspend its computation of n

!, solve the (

n

−

1

)

!

subproblem, then continue its computation of n

!. This view of the

factorial computation suggests the use of the subroutine mechanism described in

5.1.3, which has the controller use a continue register to

transfer to the part of the sequence that solves a subproblem and then continue

where it left off on the main problem. We can thus make a factorial subroutine

that returns to the entry point stored in the continue register. Around

each subroutine call, we save and restore continue just as we do the

n register, since each “level” of the factorial computation will use

the same continue register. That is, the factorial subroutine must put

a new value in continue when it calls itself for a subproblem, but it

will need the old value in order to return to the place that called it to solve

a subproblem.

借助栈，我们可以将阶乘机器的同一份数据通路复用于每个阶乘子问题。在复用操作数据通路的控制器序列方面，也存在类似的设计问题。为了重新执行阶乘计算，控制器不能像迭代型计算过程那样简单地跳回起点，因为在解决 (n−1)! 子问题之后，机器还必须将结果乘以 n。控制器必须暂停 n! 的计算，去解决 (n−1)! 子问题，然后再继续 n! 的计算。这种对阶乘计算过程的理解提示我们使用 5.1.3 节中描述的子程序机制：控制器利用 continue 寄存器跳转到处理子问题的那段序列，然后返回主问题中断处继续执行。这样，我们可以构造一个阶乘子程序，它返回到 continue 寄存器中存储的入口点。在每次子程序调用的前后，我们像保存 n 寄存器一样保存并恢复 continue，因为阶乘计算的每一“层”都将使用同一个 continue 寄存器。也就是说，阶乘子程序在为某个子问题调用自身时必须为 continue 赋予新值，但在返回调用它来处理子问题的位置时又需要用到 continue 的旧值。

Figure 5.11 shows the data paths and controller for a machine that

implements the recursive factorial procedure. The machine has a stack

and three registers, called n, val, and continue. To

simplify the data-path diagram, we have not named the register-assignment

buttons, only the stack-operation buttons (sc and sn to save

registers, rc and rn to restore registers). To operate the

machine, we put in register n the number whose factorial we wish to

compute and start the machine. When the machine reaches fact-done, the

computation is finished and the answer will be found in the val

register. In the controller sequence, n and continue are saved

before each recursive call and restored upon return from the call. Returning

from a call is accomplished by branching to the location stored in

continue. Continue is initialized when the machine starts so

that the last return will go to fact-done. The val register,

which holds the result of the factorial computation, is not saved before the

recursive call, because the old contents of val is not useful after the

subroutine returns. Only the new value, which is the value produced by the

subcomputation, is needed.

Figure 5.11: A recursive factorial machine.

图 5.11 展示了一台实现递归阶乘过程的机器的数据通路与控制器。该机器具有一个栈和三个寄存器，分别名为 n、val 和 continue。为简化数据通路图，我们未对寄存器赋值按钮命名，只对栈操作按钮命名（sc 和 sn 用于保存寄存器，rc 和 rn 用于恢复寄存器）。启动机器时，将待求阶乘的数放入寄存器 n 并启动机器。当机器到达 fact-done 时，计算完成，答案将存于寄存器 val 中。在控制器序列中，n 和 continue 在每次递归调用之前被保存，调用返回后被恢复。从调用中返回通过跳转到 continue 中存储的位置来实现。continue 在机器启动时被初始化，使得最后一次返回将跳转到 fact-done。保存阶乘计算结果的 val 寄存器在递归调用之前不需要保存，因为子程序返回后 val 的旧值已无用处。我们只需要子计算产生的新值。图 5.11：一台递归阶乘机器。

Although in principle the factorial computation requires an infinite machine,

the machine in Figure 5.11 is actually finite except for the stack, which

is potentially unbounded. Any particular physical implementation of a stack,

however, will be of finite size, and this will limit the depth of recursive

calls that can be handled by the machine. This implementation of factorial

illustrates the general strategy for realizing recursive algorithms as ordinary

register machines augmented by stacks. When a recursive subproblem is

encountered, we save on the stack the registers whose current values will be

required after the subproblem is solved, solve the recursive subproblem, then

restore the saved registers and continue execution on the main problem. The

continue register must always be saved. Whether there are other

registers that need to be saved depends on the particular machine, since not

all recursive computations need the original values of registers that are

modified during solution of the subproblem (see Exercise 5.4).

Subheading: A double recursion

尽管在理论上阶乘计算需要无限大的机器，但图 5.11 中的机器实际上是有限的，只有栈是潜在无界的。然而任何栈的具体物理实现都具有有限的大小，这将限制机器所能处理的递归调用深度。这种阶乘实现阐释了将递归算法实现为普通寄存器机器（并辅以栈）的通用策略：遇到递归子问题时，将子问题解决后仍需用到的当前寄存器值保存到栈中，求解递归子问题，然后恢复已保存的寄存器并继续主问题的执行。continue 寄存器必须始终被保存。是否还有其他寄存器需要保存，取决于具体的机器，因为并非所有递归计算在求解子问题的过程中都需要保留那些被修改的寄存器的原始值（参见练习 5.4）。子标题：双重递归

Let us examine a more complex recursive process, the tree-recursive computation

of the Fibonacci numbers, which we introduced in 1.2.2:

让我们来考察一个更复杂的递归型计算过程——Fibonacci 数的树形递归计算，我们在 1.2.2 节中已做过介绍：

Just as with factorial, we can implement the recursive Fibonacci computation as

a register machine with registers n, val, and continue.

The machine is more complex than the one for factorial, because there are two

places in the controller sequence where we need to perform recursive

calls—once to compute Fib

(

n

−

1

) and once to compute Fib

(

n

−

2

). To

set up for each of these calls, we save the registers whose values will be

needed later, set the n register to the number whose Fib we need to

compute recursively (n

−

1 or n

−

2), and assign to continue the

entry point in the main sequence to which to return (afterfib-n-1 or

afterfib-n-2, respectively). We then go to fib-loop. When we

return from the recursive call, the answer is in val. Figure 5.12

shows the controller sequence for this machine.

Figure 5.12: ↓ Controller for a machine to compute

Fibonacci numbers.

与阶乘类似，我们可以将递归 Fibonacci 计算实现为一台具有寄存器 n、val 和 continue 的寄存器机器。该机器比阶乘机器更为复杂，因为在控制器序列中有两处需要执行递归调用——一次计算 Fib(n−1)，一次计算 Fib(n−2)。为准备每次调用，我们保存之后还会用到的寄存器值，将寄存器 n 设为需要递归计算 Fib 的数（n−1 或 n−2），并将 continue 赋值为主序列中的返回入口点（分别为 afterfib-n-1 或 afterfib-n-2），然后跳转到 fib-loop。从递归调用返回后，答案存于 val 中。图 5.12 展示了该机器的控制器序列。图 5.12：↓ 计算 Fibonacci 数的机器的控制器。