25-包含一个递归调用的递归

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

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

void recurs(argumentlist)
{
      statements1
      if (test)
            recurs(arguments)
      statements2
}

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

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

程序清单7.16　recur.cpp

// recur.cpp -- using recursion
#include <iostream>
void countdown(int n);
int main()
{
    countdown(4);       // call the recursive function
    return 0;
}
void countdown(int n)
{
    using namespace std;
    cout << "Counting down ... " << n << endl;
    if (n > 0)
        countdown(n-1); // function calls itself
    cout << n << ": Kaboom!\n";
}

下面是该程序的输出：

Counting down ... 4 ‹level 1; adding levels of recursion
Counting down ... 3 ‹level 2
Counting down ... 2 ‹level 3
Counting down ... 1 ‹level 4
Counting down ... 0 ‹level 5; final recursive call
0: Kaboom!          ‹level 5; beginning to back out
1: Kaboom!          ‹level 4
2: Kaboom!          ‹level 3
3: Kaboom!          ‹level 2
4: Kaboom!          ‹level 1

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

cout << "Counting down ... " << n << " (n at " << &n << ")" << endl;
...
cout << n << ": Kaboom!" << " (n at " << &n << ")" << endl;

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

Counting down ... 4 (n at 0012FE0C)
Counting down ... 3 (n at 0012FD34)
Counting down ... 2 (n at 0012FC5C)
Counting down ... 1 (n at 0012FB84)
Counting down ... 0 (n at 0012FAAC)
0: Kaboom! (n at 0012FAAC)
1: Kaboom! (n at 0012FB84)
2: Kaboom! (n at 0012FC5C)
3: Kaboom! (n at 0012FD34)
4: Kaboom! (n at 0012FE0C)

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