加载中...

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

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


还没有评论.