Question

下面介绍一些完全不同的内容。C++函数有一种有趣的特点——可以调用自己（然而，与 C 语言不同的是，C++不允许 main( ) 调用自己），这种功能被称为递归。尽管递归在特定的编程（例如人工智能）中是一种重要的工具，但这里只简单地介绍一下它是如何工作的。

7.9.1 包含一个递归调用的递归

如果递归函数调用自己，则被调用的函数也将调用自己，这将无限循环下去，除非代码中包含终止调用链的内容。通常的方法将递归调用放在 if 语句中。例如，void 类型的递归函数 recurs( ) 的代码如下：

test 最终将为 false，调用链将断开。

递归调用将导致一系列有趣的事件。只要 if 语句为 true，每个 recurs( ) 调用都将执行 statements 1，然后再调用 recurs( )，而不会执行 statements 2。当 if 语句为 false 时，当前调用将执行 statements2。当前调用结束后，程序控制权将返回给调用它的 recurs( )，而该 recurs( ) 将执行其 stataments2 部分，然后结束，并将控制权返回给前一个调用，依此类推。因此，如果 recurs( ) 进行了 5 次递归调用，则第一个 statements1 部分将按函数调用的顺序执行 5 次，然后 statements2 部分将以与函数调用相反的顺序执行 5 次。进入 5 层递归后，程序将沿进入的路径返回。程序清单 7.16 演示了这种行为。

程序清单 7.16 recur.cpp

下面是该程序的输出：

注意，每个递归调用都创建自己的一套变量，因此当程序到达第 5 次调用时，将有 5 个独立的 n 变量，其中每个变量的值都不同。为验证这一点，读者可以修改程序清单 7.16，使之显示 n 的地址和值：

经过上述修改后，该程序的输出将与下面类似：

注意，在一个内存单元（内存地址为 0012FE0C），存储的 n 值为 4；在另一个内存单元（内存地址为 0012FD34），存储的 n 值为 3；等等。另外，注意到在 Counting down 阶段和 Kaboom 阶段的相同层级，n 的地址相同。

7.9.2 包含多个递归调用的递归

在需要将一项工作不断分为两项较小的、类似的工作时，递归非常有用。例如，请考虑使用这种方法来绘制标尺的情况。标出两端，找到中点并将其标出。然后将同样的操作用于标尺的左半部分和右半部分。如果要进一步细分，可将同样的操作用于当前的每一部分。递归方法有时被称为分而治之策略（divide-and-conquer strategy）。程序清单 7.17 使用递归函数 subdivide( ) 演示了这种方法，该函数使用一个字符串，该字符串除两端为 | 字符外，其他全部为空格。main 函数使用循环调用 subdivide( ) 函数 6 次，每次将递归层编号加 1，并打印得到的字符串。这样，每行输出表示一层递归。该程序使用限定符 std::而不是编译指令 using，以提醒读者还可以采取这种方式。

程序清单 7.17 ruler.cpp

下面是程序清单 7.17 中程序的输出：

程序说明

在程序清单 7.17 中，subdivide( ) 函数使用变量 level 来控制递归层。函数调用自身时，将把 level 减 1，当 level 为 0 时，该函数将不再调用自己。注意，subdivide( ) 调用自己两次，一次针对左半部分，另一次针对右半部分。最初的中点被用作一次调用的右端点和另一次调用的左端点。请注意，调用次数将呈几何级数增长。也就是说，调用一次导致两个调用，然后导致 4 个调用，再导致 8 个调用，依此类推。这就是 6 层调用能够填充 64 个元素的原因（2⁶=64）。这将不断导致函数调用数（以及存储的变量数）翻倍，因此如果要求的递归层次很多，这种递归方式将是一种糟糕的选择；然而，如果递归层次较少，这将是一种精致而简单的选择。