2.1.3 递归不够快

递归是算法设计和问题求解中一个强有力的工具（更多递归程序的内容阅读4.1节）。首先，很多数学函数是递归定义的，如阶乘函数（n!=n×(n−1)!）。其次，有的数据结构（如二叉树、广义表等）本身具备递归特性，它们的操作可递归地描述。最后，有一些问题，虽然问题本身没有明显的递归结构，但是递归求解比迭代求解更简单和直观，如N皇后问题、Hanoi塔问题等。

虽然递归程序代码简洁，但是它的执行效率（运行所需的时间和空间）往往不是很令人满意。递归程序的低效主要来源于两方面。

首先，递归调用需要额外的时间和空间开销。通常，一个函数在调用另一个函数之前，要做如下事情：① 将实际参数、返回地址等信息传递给被调用函数保存；② 为被调用函数的局部变量分配存储空间；③ 将控制转移到被调用函数的入口。

同时，从被调用函数返回调用函数之前，也要做三件事情：① 保存被调用函数的计算结果；② 释放被调用函数的数据区内存空间；③ 依照被调用函数保存的返回地址将控制转移到调用函数。

在这些事项中，保存变量和地址信息需要占用系统栈空间，控制转移需要一定的时间开销。在递归调用时，尤其是递归调用的深度比较大时，时间和空间开销就会激增成一个相当可观的量。

其次，递归算法中的子问题可能重复计算。递归的基本原理是把一个规模很大的问题转换为同样形式但规模小一些的子问题，然后递归处理。如果这些子问题不是相互独立的，而是相互之间有重叠，那么，简单地递归求解会导致子问题的重复计算，造成算法效率的低下。下面看一个例子。

【例2-3】 Fibonacci函数

问题描述：Fibonacci函数Fib(n)定义如下：

输入：自变量n（n<50）。

输出：Fibonacci数值Fib(n)。

显然，Fibonacci函数本身就是一个递归定义的函数，其递归代码见程序2-6。

程序2-6 Fibonacci函数递归程序

运行这段程序可知，尽管计算结果正确，但是程序在计算效率上比较低。随着n的增加，计算所需的时间迅速增加。图2-2展示了Fib(5)的递归调用过程，递归调用的深度等于4，其中Fib(3)有2次调用，Fib(2)有3次调用，总共的函数调用有15次。仔细观察可以发现，Fib(3)和Fib(2)存在重复调用。

图2-2 Fib(5)的递归调用过程示意图

从表2-2可以看出，函数的调用次数随着参数n的增加呈指数级增长，输入参数每增加5，其递归函数的调用次数就增大10倍以上。在程序2-6中，当iN大于1时，其函数值都需要递归调用，因此会造成非常巨大的重复递归调用。这种重复计算随着n值的增加而爆炸式地增长。

表2-2 Fibonacci函数的调用次数

虽然部分编译器提供了对递归调用的优化处理，也就是说，可以从系统层面提高递归算法的执行效率。但是如果一个递归算法存在大量子问题的重复计算，则计算机系统无法提供优化，需要设计者改善算法，如使用动态规划方法（见第5章）避免子问题重复计算。