由 釋出
2013 年 6 月 21 日 (最後更新：2013 年 6 月 25 日)

遞迴

評分：3.9/5 (2744 票)
*****

遞迴


什麼是遞迴？簡單來說，就是函式呼叫自身。但它是如何發生的？為什麼會發生，它的用途又是什麼？

當我們談論遞迴時，我們實際上是在談論建立迴圈。讓我們從一個基本的迴圈開始。

1
2
3
 
for(int i=0;  i<10; i++) {
     cout << "The number is: " << i << endl;
}


對於還不知道的人來說，這個基本迴圈會顯示句子“The number is: ”，後面跟著“i”的值。就像這樣。

The number is: 0
The number is: 1
The number is: 2
The number is: 3
The number is: 4
The number is: 5
The number is: 6
The number is: 7
The number is: 8
The number is: 9

在“for 迴圈”宣告內部，我們有整型變數“i”，並將其初始值設定為 0。因此，第一次顯示句子時，它顯示“The number is: 0”。“for 迴圈”宣告中“i++”的部分告訴程式，每次迴圈重複時，“i”的值都會增加 1。所以，下次顯示句子時，它顯示“The number is: 1”。
這個週期會一直重複，只要“i”的值小於 10。最後顯示的句子將是“The number is: 9”。正如你所見，基本的“for 迴圈”宣告有三個部分：一個初始值，繼續重複必須保持的條件，以及一個修改表示式。包含在 {} 中的是程式執行的操作。Cout 是 console out（控制檯輸出）的縮寫，用於將單詞或字元列印到螢幕上。
那麼這與遞迴有什麼關係呢？記住，遞迴就是迴圈。如果我不想僅僅在螢幕上列印一條訊息怎麼辦？迴圈還可以用於執行其他任務。

下面的程式碼是與上面相同的迴圈，只是現在它被用來呼叫一個函式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
using namespace std;

void numberFunction(int i) {
  cout << "The number is: " << i << endl;
}

int main() {

for(int i=0; i<10; i++) {
  numberFunction(i);
}

return 0;
}


我聲明瞭一個 void 函式，這意味著它不返回任何值，並且接受一個 int i 引數。該函式名為 numberFunction，如你所見，它所做的只是顯示句子“The number is: ”，後面跟著“i”的當前值。“for 迴圈”呼叫該函式，只要“i”的值小於 10，就會不斷地呼叫該函式。

現在，透過遞迴，我們就不需要使用“for 迴圈”了，因為我們將進行設定，使我們的函式呼叫自身。讓我們再重做一遍相同的程式，只是這次我們將在沒有“for 迴圈”的情況下進行。我們將使用遞迴迴圈，就像這樣。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
using namespace std;

void numberFunction(int i) {
  cout << "The number is: " << i << endl;
  i++;
  if(i<10) {
    numberFunction(i);
  }
}

int main() {

int i = 0;
numberFunction(i);

return 0;
}


我們做到了！我們使用了遞迴！你可以看到 numberFunction 的呼叫只在程式的 main 部分進行了一次，但它從函式內部不斷地被一次又一次地呼叫，只要 i 小於 10。