Excel VBA 编程基础 -- 过程与函数(七)

今天我们讨论一种特殊的 Sub/Function：自己调用自己的过程。

这种“自己调用自己”的过程，称为递归过程（recursive procedures）。

例1. 阶乘函数（计算 n 的阶乘 n!）

Function Factorial(ByVal n As Long) As Long  If n >1Then    Factorial = n * Factorial(n -1)Else    Factorial =1End IfEndFunction

我们知道，n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n。阶乘计算本质上具有递归性，因此用递归函数来计算 n! 最为直观，如上面的代码所示。

完整的示例如下图：

图1 阶乘函数

为了明了递归函数的执行过程，我们特意在 Factorial 的开头用 Debug.Print 把 n 的值打印出来。从立即窗口的执行结果可以看出，在 FactorialTest 中以 n = 10 作为实参调用 Factorial，此时形参 n 的值是 10，然后在 Factorial 中又以 n - 1 作为实参调用 Factorial，再次进入 Factorial 后，形参 n 的值是 9，然后再次以 n - 1 作为实参调用自身，如此重复，直到 n = 1 时，此时 Factorial 不再递归调用自身，而是直接返回一个确定的值 1。

在 Factorial 返回 1 之前，所有的 n 值都是存在栈里的。因为每一次过程调用都要创建一个栈帧（stack frame），用来存放过程的局部变量（譬如 Factorial 函数的形参 n）以及返回地址。

Factorial 因为是递归调用，因此直到 n = 1 时，Factorial 才真正返回到调用者，也就是说，在这之前，Factorial 是一层套一层，已经积累了 10 层的栈帧。每一层都有一个 n 的值。直到 n = 1 才开始一层一层地返回（即回退），相应地，阶乘也才从 1 开始逐步乘上去：1 * 2 * 3 * ……。

从以上的叙述，可以看出，Factorial 函数实际上有两个过程：

一层一层嵌套下去，乘积的展开：n * (n-1) * …… * 3 * 2 * 1
一层一层回退回来，乘积的完成：1 * 2 * 3 * …… * (n - 1) * n

当然，阶乘也可以用循环来实现，而且效率比递归还要高。

下面再来看一个具有本质递归性的函数例子。

例2. 斐波那契数的计算

斐波那契数列定义如下：

F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

用自然语言叙述，即从第三项开始，每一项都是前两项之和。

很显然，斐波那契数 F(n) 的计算很适合用递归来实现。代码如下图：

图2 计算斐波那契数

如图所示，函数 Fibonacci 实现为一个递归函数，该递归函数的终结条件是 n = 0 或 n = 1，然后函数逐级回退，实现 F(1) + F(0) => F(2)，F(2) + F(1) => F(3)，……，F(n-1) + F(n-2) => F(n)。

递归过程因为需要一层一层深入，一直到最终的终结条件，然后再一层一层回退。每一层都需要一个栈帧来保存过程的参数、局部变量、返回地址等信息。因此，递归过程需要大量的栈空间，特别对于递归深度较深以及递归过程规模较大的情形，极端情况是过程没有终结条件或终结条件无法满足，以至于递归无法终结，递归过程会一直层层嵌套下去，直到耗尽栈空间，程序崩溃为止。

所以，写递归过程一定要注意递归终结条件的可满足性。另外就是尽量减少递归过程的参数及局部变量，也就是尽量减少栈帧的空间。