4.7 递归

上章中我提到一个函数调用另一个函数是符合语法的，而且我们已经见过好几个例子。但我还没有告诉你们，一个函数调用它自己也是合法的。这是件好事，理由可能不那么显而易见，但事实证明它是一个程序能做的最具魔力也最有趣的事情之一。

例如，下面这个函数：

void countdown( int n) {
  if (n == 0) {
    cout << "Blastoff! << endl;
  } else {
    cout << n << endl;
    countdown (n-1);
  } 
}

函数名是countdown，它把单个整数作为参数，如果参数是0，则输出单词“Blastoff”。否则输出这个参数，然后调用countdown函数--也即它自身--传入n-1作为输入参数。

如果我们这么调用这函数，会发生什么呢？

void main ()
{
  countdown (3);
}

countdown从n=3开始执行，由于n不为0，所以它输出值3，然后调用它自己...

countdown从n=2开始执行，由于n不为0，所以它输出值2，然后调用它自己...

countdown从n=1开始执行，由于n不为0，所以它输出值2，然后调用它自己...

countdown从n=0开始执行，由于n为0，所以它输出单词“Blastoff!”，然后返回。

countdown得到返回值n=1。

countdown得到返回值n=2。

countdown得到返回值n=3。

然后你会回到main函数（多美妙的一次旅行！）。因此输出看起来会是这样：

3
2
1
“Blastoff!”

作为第二个例子，让我们再来看看函数newLine和threeLine。

void newLine() [
  cout << endl;
}

void threeLine() {
   newLine();   new Line();   new Line();
}

尽管它们奏效，但如果我希望再输出2个或者106个换行符，它们并不能帮我们太多。一种更好的替代方法是这样：

void nLines(int n){
  if (n > 0) {
     cout << endl;
     nLines (n-1);    
  }
}

这段程序和countdown很相似，只要n大于0，它就会输出一个换行符，然后调用它自身来输出另外的n-1行。因此，总的换行符个数是1+(n-1), 最后得到n

一个函数调用它自身的过程被称为递归，这些函数被称为递归的。