MAGICALBOY

今天看了某 C 语言 Primer 教材中一递归（recursion）示例运行结果，一开始让我迷惑不解，后来才发觉原来我一直不懂递归。枉我之前还写过递归读取树结构的文件目录的 Python 脚本（还好是尾随递归，所以不会出问题，惭愧）！且看代码清单如下：

/* recursion.c -- 递归演示 */ /* 程序显示递归的级数 n 及存储 n 的内存地址 */ #include void recursion(int); int main(void) { recursion(1); return 0; } void recursion(int n) { printf("第%d级递归: n 内存地址 %p\n", n, &n); if (n < 4) recursion(n+1); // 注意此处 n+1 并不等于 ++n! printf("第%d级递归: n 内存地址 %p\n", n, &n); }

第1级递归: n 内存地址 0022FF30 第2级递归: n 内存地址 0022FF10 第3级递归: n 内存地址 0022FEF0 第4级递归: n 内存地址 0022FED0 第4级递归: n 内存地址 0022FED0 第3级递归: n 内存地址 0022FEF0 第2级递归: n 内存地址 0022FF10 第1级递归: n 内存地址 0022FF30

递归函数即是直接或间接调用自身的函数。在上面的程序中，recursion() 递归函数定义代码中，局部变量 n<4 不是正好调用自己三次打印 3 次，另加上 if 控制语句外的 1 条打印语句，应该是打印输出 4 打语句才对的啊，Why？

如果有人和我开始的想法一样，那下面开始分析。

首先看调用函数 main() 中，使用参数 1 调用了 recursion() 函数。recursion() 的形参 n 为 1，故打印输出的 n 值为 1。接着由于 n=1<4，第一级递归使用 n=n+1 即 n=2 调用 recursion(), 使得 n 在第二级中调用被赋值为 2，打印输出 n 的值为 2。依此类推，下面的调用输出的为第 3 级递归和第 4 级递归。

这都没问题，好，继续看当开始执行第四级调用时，此时 n=4，由于 n<4 不成立不再调用 recursion() 函数，直接执行下面的语句，输出：“第4级递归...”。现在看关键的地方，第四级递归调用至此已经执行完毕了，那接着做些什么事呢。按我们开始的想法是函数调用结束，回到调用函数 main() 整个程序运行结束。问题正是出于此，当第四级调用结束会把返回给当前被调用函数（即第四级递归）的调用函数（即第三级递归），而非直接返回到第一级递归调用的 main() 函数！，就这么简单的逻辑却被我们忽略了，哈哈

同时注意到第层的调用中 n 的内存地址有所变化，说明每一级的递归使用的是它自己的私有变量。

如果是刚接触递归可能会有些迷惑，使用递归必须注意几点：

• 递归可以使程序结构简单，但递归的执行效率没有循环语句高，需注意使用。
• 递归每一级函数的调用都有它自己的私有变量。
• 每一次函数调用完都有一次返回，这是容易疏忽的一点。
• 递归调用前的语句和各级被调用函数具有相同的执行顺序。这点看输出结果就知道了，不难理解。
• 递归调用后的语句和各级被调用函数的执行顺序相反。
• 递归的深度不宜太深，会很快消耗掉计算机资源。同时必须包含终止递归的语句。