18-演示递归

9.3.1　演示递归

我们通过一个程序示例，来学习什么是递归。程序清单9.6中的 main() 函数调用 up_and_down() 函数，这次调用称为“第1级递归”。然后 up_and_down() 调用自己，这次调用称为“第2级递归”。接着第2级递归调用第3级递归，以此类推。该程序示例共有4级递归。为了进一步深入研究递归时发生了什么，程序不仅显示了变量 n 的值，还显示了存储 n 的内存地址 &n 。（本章稍后会详细讨论 & 运算符， printf() 函数使用 %p 转换说明打印地址，如果你的系统不支持这种格式，请使用 %u 或 %lu 代替 %p ）。

程序清单9.6　 recur.c 程序

/* recur.c -- 递归演示 */
#include <stdio.h>
void up_and_down(int);
int main(void)
{
     up_and_down(1);
     return 0;
}
void up_and_down(int n)
{
     printf("Level %d: n location %p\n", n, &n); // #1
     if (n < 4)
          up_and_down(n + 1);
     printf("LEVEL %d: n location %p\n", n, &n); // #2
}

下面是在我们系统中的输出：

Level 1: n location 0x0012ff48
Level 2: n location 0x0012ff3c
Level 3: n location 0x0012ff30
Level 4: n location 0x0012ff24
LEVEL 4: n location 0x0012ff24
LEVEL 3: n location 0x0012ff30
LEVEL 2: n location 0x0012ff3c
LEVEL 1: n location 0x0012ff48

我们来仔细分析程序中的递归是如何工作的。首先， main() 调用了带参数 1 的 up_and_down() 函数，执行结果是 up_and_down() 中的形式参数 n 的值是 1 ，所以打印语句 #1 打印 Level 1 。然后，由于 n 小于 4 ， up_and_down() （第1级）调用实际参数为 n + 1 （或 2 ）的 up_and_down() （第2级）。于是第2级调用中的 n 的值是 2 ，打印语句 #1 打印 Level 2 。与此类似，下面两次调用打印的分别是 Level 3 和 Level 4 。

当执行到第4级时， n 的值是 4 ，所以 if 测试条件为假。 up_and_down() 函数不再调用自己。第 4 级调用接着执行打印语句 #2 ，即打印 LEVEL 4 ，因为 n 的值是 4 。此时，第4级调用结束，控制被传回它的主调函数（即第3级调用）。在第3级调用中，执行的最后一条语句是调用 if 语句中的第4级调用。被调函数（第4级调用）把控制返回在这个位置，因此，第3级调用继续执行后面的代码，打印语句 #2 打印 LEVEL 3 。然后第3级调用结束，控制被传回第2级调用，接着打印 LEVEL 2 ，以此类推。

注意，每级递归的变量 n 都属于本级递归私有。这从程序输出的地址值可以看出（当然，不同的系统表示的地址格式不同，这里关键要注意， Level 1 和 LEVEL 1 的地址相同， Level 2 和 LEVEL 2 的地址相同，等等）。

如果觉得不好理解，可以假设有一条函数调用链—— fun1() 调用 fun2() 、 fun2() 调用 fun3() 、 fun3() 调用 fun4() 。当 fun4() 结束时，控制传回 fun3() ；当 fun3() 结束时，控制传回 fun2() ；当 fun2() 结束时，控制传回 fun1() 。递归的情况与此类似，只不过 fun1() 、 fun2() 、 fun3() 和 fun4() 都是相同的函数。