1.2.2 树形递归

另一种常见计算模式称为树形递归。作为例子，现在考虑斐波那契（Fibonacci）数序列的计算，这一序列中的每个数都是前面两个数之和：

0, 1, 1, 2, 3, 5, 8, 13, 21,…

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

我们立刻就能把这个定义翻译为一个计算斐波那契数的递归函数：

现在考虑这一计算的模式。为了计算fib（5），我们需要计算fib（4）和fib（3）。而为了计算fib（4），又需要计算fib（3）和fib（2）。一般而言，这一演化过程看起来像一棵树，如图1.5所示。请注意，这里的分支在每一层分裂为两个分支（除了最下面的），反映出对fib函数的每个调用里两次递归调用自身的事实。

上面这个函数作为典型的树形递归很有教育意义，但对计算斐波那契数而言，它却是一种很糟糕的方法，因为做了太多的冗余计算。从图1.5中可以看到，对fib（3）的全部计算重复做了两次，差不多占到所有工作的一半。事实上，不难证明，在整个计算过程中，计算fib（1）和fib（0）的次数（一般来说，也就是上面这种树里的树叶数）正好是Fib（n+1）。要感受一下这种情况有多糟，我们可以证明Fib（n）值的增长相对于n是指数的。更准确地说（见练习1.13），Fib（n）等于最接近的那个整数，其中：

这也就是黄金分割的值，它满足方程：

ϕ2=ϕ+1

这样，这个计算过程中所用的步骤数将随着输入的增长而指数增长。在另一方面，其空间需求只是随着输入的增长而线性增长，因为，在计算中的每一点，我们都只需要保存树中在此结点之上的结点的轨迹。一般而言，树形递归计算过程里所需要的步骤数正比于树中的结点数，其空间需求正比于树的最大深度。

我们也可以规划出一种计算斐波那契数的迭代计算过程，其基本想法就是用一对整数a和b，把它们分别初始化为Fib（1）=1和Fib（0）=0，然后反复地同时应用下面的变换规则：

a←a+b

b←a

不难证明，在n次应用这些变换后，a和b将分别等于Fib（n+1）和Fib（n）。因此，我们可以定义下面这两个函数，以迭代方式计算斐波那契数：

这种计算Fib（n）的方法是线性迭代。这两种方法在所需步数上差异巨大——后一个相对n为线性的，前一个增长得如Fib（n）一样快——即使不大的输入也可能造成巨大差异。

然而，我们也不应该做出结论说树形递归计算过程根本没用。如果需要考虑操作具有层次结构的数据（而不是操作数值），我们可能发现树形递归计算过程是一种很自然的、威力强大的工具[30]。即使对于数的计算，树形递归计算过程也可能帮助我们理解和设计程序。以计算斐波那契数的程序为例，虽然第一个fib函数远比第二个低效，但它却更直截了当，几乎就是把斐波那契序列的定义直接翻译为JavaScript。而要规划出对应的迭代算法，就需要注意到该计算过程可以重塑为一个采用三个状态变量的迭代。

实例：换零钱方式的统计

要找到迭代的斐波那契算法，只需要不多的智慧。下面这个问题的情况与此不同：我们有一些50美分、25美分、10美分、5美分和1美分的硬币，要把1美元换成零钱，一共有多少种不同的方式？更一般的问题是，给了任意数量的美元现金，我们能写出一个程序，计算出所有换零钱方式的数目吗？

如果采用递归函数，这个问题有一种很简单的解法。假定我们把考虑的可用硬币类按某种顺序排好，于是就有下面的关系。

把总数为a的现金换成n种硬币的不同方式的数目等于

现金a换成除去第一种硬币之外的所有其他硬币的不同方式数目

加上现金a-d换成所有种类的硬币的不同方式数目，其中d是第一种硬币的币值

要弄清为什么这一说法正确，请注意这里把换零钱的方式分成两组，第一组的换法都没用第一种硬币，而第二组都用了第一种硬币。显然，换零钱的全部换法的数目，就等于完全不用第一种硬币的换法数，加上用了第一种硬币的换零钱的换法数。而后一个数目也就等于去掉一个第一种硬币值后，将剩下的现金换零钱的换法数。

这样，我们就把某个给定现金数的换零钱方式的问题，递归地归约为对更少现金数或者更少硬币种类的同一个问题。请仔细考虑上面的归约规则，设法使自己确信，如果采用下面的方法处理各种退化情况，我们就能利用上述规则写出一个算法[31]：

●如果a就是0，应该算作有1种换零钱的方式。

●如果a小于0，应该算作有0种换零钱的方式。

●如果n是0，应该算作有0种换零钱的方式。

我们很容易把这些规则翻译成一个递归函数：

（函数first_denomination以可用硬币的种类数作为输入，返回第一种硬币的币值。这里认为硬币已经从最小到最大排好了，其实采用任何顺序都可以。）我们现在就能回答开始的问题了，下面是1美元换硬币的不同方法的数目：

函数count_change产生树形递归的计算过程，其中的冗余计算与前面fib的第一种实现类似。但另一方面，想设计一个能算出同样结果的更好的算法，就不那么明显了。我们把这个问题留给读者作为一个挑战。可以看到，树形递归的计算过程可能极其低效，但常常很容易描述和理解，这导致有人提出能否利用这两个世界里最好的东西设计一种“聪明编译器”，使之能把树形递归的函数翻译为能完成同样计算的更高效的函数[32]。

练习1.11 函数f由如下规则定义：如果n<3，那么f（n）=n；如果n≥3，那么f（n）=f（n-1）+2f（n-2）+3f（n-3）。请写一个JavaScript函数，它通过一个递归计算过程计算f。再写一个函数，通过迭代计算过程计算f。

练习1.12 下面的数值模式称为帕斯卡三角形：

三角形两个斜边上的数都是1，内部的每个数是位于它上面的两个数之和[33]。请写一个函数，它通过一个递归计算过程计算帕斯卡三角形。

练习1.13 证明Fib（n）是最接近的整数，其中。提示：利用归纳法和斐波那契数的定义（见1.2.2节），证明，其中。