C++ 遞歸

上章中我提到一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)是符合語法的，而且我們已經(jīng)見過好幾個(gè)例子。但我還沒有告訴你們，一個(gè)函數(shù)調(diào)用它自己也是合法的。這是件好事，理由可能不那么顯而易見，但事實(shí)證明它是一個(gè)程序能做的最具魔力也最有趣的事情之一。

例如，下面這個(gè)函數(shù)：

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

函數(shù)名是countdown，它把單個(gè)整數(shù)作為參數(shù)，如果參數(shù)是0，則輸出單詞“Blastoff”。否則輸出這個(gè)參數(shù)，然后調(diào)用countdown函數(shù)--也即它自身--傳入n-1作為輸入?yún)?shù)。

如果我們這么調(diào)用這函數(shù)，會(huì)發(fā)生什么呢？

void main ()
{
  countdown (3);
}

countdown從n=3開始執(zhí)行，由于n不為0，所以它輸出值3，然后調(diào)用它自己...

countdown從n=2開始執(zhí)行，由于n不為0，所以它輸出值2，然后調(diào)用它自己...

countdown從n=1開始執(zhí)行，由于n不為0，所以它輸出值2，然后調(diào)用它自己...

countdown從n=0開始執(zhí)行，由于n為0，所以它輸出單詞“Blastoff!”，然后返回。

countdown得到返回值n=1。

countdown得到返回值n=2。

countdown得到返回值n=3。

然后你會(huì)回到main函數(shù)（多美妙的一次旅行?。Ｒ虼溯敵隹雌饋頃?huì)是這樣：

3
2
1
“Blastoff!”

作為第二個(gè)例子，讓我們再來看看函數(shù)newLine和threeLine。

void newLine() [
  cout << endl;
}

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

盡管它們奏效，但如果我希望再輸出2個(gè)或者106個(gè)換行符，它們并不能幫我們太多。一種更好的替代方法是這樣：

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

這段程序和countdown很相似，只要n大于0，它就會(huì)輸出一個(gè)換行符，然后調(diào)用它自身來輸出另外的n-1行。因此，總的換行符個(gè)數(shù)是1+(n-1), 最后得到n

一個(gè)函數(shù)調(diào)用它自身的過程被稱為遞歸，這些函數(shù)被稱為遞歸的。