1.2.2 Tree Recursion

Another common pattern of computation is called

tree recursion. As

an example, consider computing the sequence of Fibonacci numbers, in which each

number is the sum of the preceding two:

另一种常见的计算模式称为树形递归 (tree recursion)。以计算斐波那契数列为例，该数列中每个数都是前两个数之和：

In general, the Fibonacci numbers can be defined by the rule

一般而言，斐波那契数可由如下规则定义：

Fib
(
n
)

=

{

0

if

若

n
=
0
,
n
=
0
，

1

if

若

n
=
1
,
n
=
1
，

Fib
(
n
−
1
)
+
Fib
(
n
−
2
)

otherwise

.

否则。

We can immediately translate this definition into a recursive procedure for

computing Fibonacci numbers:

我们可以直接将这个定义转化为计算斐波那契数的递归型过程：

Consider the pattern of this computation. To compute (fib 5), we

compute (fib 4) and (fib 3). To compute (fib 4), we

compute (fib 3) and (fib 2). In general, the evolved process

looks like a tree, as shown in Figure 1.5. Notice that the branches

split into two at each level (except at the bottom); this reflects the fact

that the fib procedure calls itself twice each time it is invoked.

Figure 1.5: The tree-recursive process generated in computing (fib 5).

考察这个计算的模式。要计算 `(fib 5)`，需要计算 `(fib 4)` 和 `(fib 3)`；要计算 `(fib 4)`，需要计算 `(fib 3)` 和 `(fib 2)`。一般而言，演化出的计算过程形如一棵树，如图 1.5 所示。注意每一层的分支都一分为二（底层除外），这反映了 fib 过程每次调用时都会调用自身两次这一事实。图 1.5：计算 `(fib 5)` 时产生的树形递归型计算过程。

This procedure is instructive as a prototypical tree recursion, but it is a

terrible way to compute Fibonacci numbers because it does so much redundant

computation. Notice in Figure 1.5 that the entire computation of

(fib 3)—almost half the work—is duplicated. In fact, it is not hard

to show that the number of times the procedure will compute (fib 1) or

(fib 0) (the number of leaves in the above tree, in general) is

precisely Fib

(

n

+

1

). To get an idea of how bad this is, one can

show that the value of Fib

(

n

) grows exponentially with n. More

precisely (see Exercise 1.13), Fib

(

n

) is the closest integer

to φ

n

这个过程作为树形递归的典型范例很有启发意义，但用它来计算斐波那契数却极为低效，因为它包含大量重复计算。从图 1.5 可以看出，`(fib 3)` 的整个计算——几乎占了一半的工作量——被重复进行了一次。事实上，不难证明，过程计算 `(fib 1)` 或 `(fib 0)` 的次数（即上述树中叶子节点的总数）恰好是 Fib(n + 1)。为了说明这有多糟糕，可以证明 Fib(n) 随 n 指数增长。更精确地说（见练习 1.13），Fib(n) 是最接近 φⁿ

/

5, where

√5 的整数，其中

φ

=

1
+

5

2

≈

1.6180

is the

golden ratio, which satisfies the equation

即黄金比例 (golden ratio)，满足方程

φ
2

=

φ
+
1.
φ
+
1。

Thus, the process uses a number of steps that grows exponentially with the

input. On the other hand, the space required grows only linearly with the

input, because we need keep track only of which nodes are above us in the tree

at any point in the computation. In general, the number of steps required by a

tree-recursive process will be proportional to the number of nodes in the tree,

while the space required will be proportional to the maximum depth of the tree.

由此可见，该计算过程所需步骤数随输入呈指数增长。另一方面，所需空间只随输入线性增长，因为在计算过程的任意时刻，我们只需记录树中当前节点之上的那些节点。一般而言，树形递归型计算过程所需的步骤数正比于树中的节点数，而所需空间则正比于树的最大深度。

We can also formulate an iterative process for computing the Fibonacci numbers.

The idea is to use a pair of integers a and b, initialized to

Fib(1) = 1 and Fib(0) = 0, and to repeatedly apply the

simultaneous transformations

我们也可以为计算斐波那契数构造出一个迭代型计算过程。其思路是用一对整数 a 和 b，分别初始化为 Fib(1) = 1 和 Fib(0) = 0，然后反复同时应用如下变换

It is not hard to show that, after applying this transformation n times,

a and b will be equal, respectively, to Fib

(

n

+

1

) and

Fib

(

n

). Thus, we can compute Fibonacci numbers iteratively using

the procedure

不难证明，将此变换应用 n 次之后，a 和 b 将分别等于 Fib(n + 1) 和 Fib(n)。于是，我们可以用下面的过程来迭代地计算斐波那契数

This second method for computing Fib

(

n

) is a linear iteration. The

difference in number of steps required by the two methods—one linear in

n, one growing as fast as Fib

(

n

) itself—is enormous, even for

small inputs.

计算 Fib(n) 的第二种方法是线性迭代型计算过程。两种方法所需步骤数之差——一个与 n 成线性关系，另一个增长速度和 Fib(n) 本身一样快——即使对于较小的输入也已相当悬殊。

One should not conclude from this that tree-recursive processes are useless.

When we consider processes that operate on hierarchically structured data

rather than numbers, we will find that tree recursion is a natural and powerful

tool. But

even in numerical operations, tree-recursive processes can be useful in helping

us to understand and design programs. For instance, although the first

fib procedure is much less efficient than the second one, it is more

straightforward, being little more than a translation into Lisp of the

definition of the Fibonacci sequence. To formulate the iterative algorithm

required noticing that the computation could be recast as an iteration with

three state variables.

Subheading: Example: Counting change

不应由此得出树形递归型计算过程毫无用处的结论。当我们考虑的是对层级结构数据而非数值进行操作的计算过程时，会发现树形递归 (tree recursion) 是一种自然而强大的工具。但即便在数值运算中，树形递归型计算过程也有助于我们理解和设计程序。例如，尽管第一个 fib 过程远不如第二个高效，它却更加直观，几乎就是斐波那契数列定义的 Lisp 直译。而构造迭代算法则需要发现：这一计算可以被改写为带三个状态变量的迭代形式。

小节标题：示例：换零钱的方法数

It takes only a bit of cleverness to come up with the iterative Fibonacci

algorithm. In contrast, consider the following problem: How many different

ways can we make change of $1.00, given half-dollars, quarters, dimes,

nickels, and pennies? More generally, can we write a procedure to compute the

number of ways to change any given amount of money?

想出迭代的斐波那契算法只需一点小聪明。相比之下，请考虑以下问题：给定半美元、25 美分、10 美分、5 美分和 1 美分硬币，将 1 美元换成零钱共有多少种不同的方式？更一般地，我们能写出一个过程来计算将任意金额换成零钱的方法数吗？

This problem has a simple solution as a recursive procedure. Suppose we think

of the types of coins available as arranged in some order. Then the following

relation holds:

The number of ways to change amount a using n kinds of coins equals

这个问题有一个简单的递归过程解法。假设我们将可用的硬币种类按某种顺序排列，则下面的关系成立：

用 n 种硬币将金额 a 换成零钱的方法数等于

the number of ways to change amount a using all but the first kind of coin,

plus

不使用第一种硬币、将金额 a 换成零钱的方法数，加上

the number of ways to change amount a

−

d using all n kinds of

coins, where d is the denomination of the first kind of coin.

用全部 n 种硬币将金额 a − d 换成零钱的方法数，其中 d 是第一种硬币的面值。

To see why this is true, observe that the ways to make change can be divided

into two groups: those that do not use any of the first kind of coin, and those

that do. Therefore, the total number of ways to make change for some amount is

equal to the number of ways to make change for the amount without using any of

the first kind of coin, plus the number of ways to make change assuming that we

do use the first kind of coin. But the latter number is equal to the number of

ways to make change for the amount that remains after using a coin of the first

kind.

要理解为何如此，请注意：换零钱的方式可以分为两组——不使用任何第一种硬币的，以及使用了第一种硬币的。因此，将某一金额换成零钱的方法总数，等于不使用第一种硬币时的换法数，加上假设使用了第一种硬币时的换法数。而后者恰好等于用完一枚第一种硬币之后剩余金额的换法数。

Thus, we can recursively reduce the problem of changing a given amount to the

problem of changing smaller amounts using fewer kinds of coins. Consider this

reduction rule carefully, and convince yourself that we can use it to describe

an algorithm if we specify the following degenerate cases:

这样，我们可以递归地将换零钱问题归约为用更少种类硬币换更小金额的问题。仔细审视这条归约规则，说服自己：只要明确以下几种退化情形，就可以用它描述一个算法：

If a is exactly 0, we should count that as 1 way to make change.

若 a 恰好等于 0，应计为 1 种换法。

If a is less than 0, we should count that as 0 ways to make change.

若 a 小于 0，应计为 0 种换法。

If n is 0, we should count that as 0 ways to make change.

We can easily translate this description into a recursive procedure:

若 n 等于 0，应计为 0 种换法。

我们可以很容易地将上述描述翻译成一个递归过程：

(The first-denomination procedure takes as input the number of kinds of

coins available and returns the denomination of the first kind. Here we are

thinking of the coins as arranged in order from largest to smallest, but any

order would do as well.) We can now answer our original question about

changing a dollar:

（过程 first-denomination 以可用硬币种数为输入，返回第一种硬币的面值。这里我们将硬币按面值从大到小排列，但任何顺序都同样可行。）现在我们可以回答最初关于换 1 美元零钱的问题了：

Count-change generates a tree-recursive process with redundancies

similar to those in our first implementation of fib. (It will take

quite a while for that 292 to be computed.) On the other hand, it is not

obvious how to design a better algorithm for computing the result, and we leave

this problem as a challenge. The observation that a tree-recursive process may

be highly inefficient but often easy to specify and understand has led people

to propose that one could get the best of both worlds by designing a “smart

compiler” that could transform tree-recursive procedures into more efficient

procedures that compute the same result.

count-change 生成一个树形递归型计算过程，其中存在类似于第一个 fib 实现中的冗余计算。（计算出那个 292 需要相当长的时间。）另一方面，如何设计一个更好的算法来计算结果并不显而易见，我们将此留作挑战。树形递归型计算过程可能效率极低，却往往易于描述和理解——这一观察促使人们提出：或许可以设计一种"智能编译器"，将树形递归型过程变换为计算相同结果的更高效过程，从而兼得两者之长。