遞迴
什麼是遞迴？
自己呼叫自己
從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？「從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？『從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？……』」
這個故事一直不停的說一直不停的說同一個故事，說到什麼時候停止？聽故事的人聽到不耐煩，不想再聽為止。
終止條件
所以要設定一個結束故事的條件，假設講了10次故事，聽故事的人就不想聽了，作為終止條件。
次數
每一次講故事的次數怎麼傳進去？通常使用參數傳進去講故事的函式，每講一次，就把前面講過的故事總次數加1，呼叫下一個講故事的函式中。
講故事(1) -> 講故事(1+1) -> 講故事(2+1) -> 講故事(3+1) -> 講故事(4+1) -> 講故事(5+1) -> 講故事(6+1) -> 講故事(7+1) -> 講故事(8+1) -> 講故事(9+1) -> 講故事(10+1) -> 已經講了10次，終止講故事。
1
2
3
4
5
6
7
8
9
10
void story(int count) {
if(count > 10) return;
cout << "第" << count << "次:";
cout << "從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？" << endl;
story(count + 1);
}
int main() {
story(1);
return 0;
}
第1次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第2次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第3次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第4次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第5次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第6次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第7次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第8次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第9次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第10次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
二種遞迴
傳遞函式前處理
士兵長對10個士兵說，把前面的人的子彈總數加上自己手上的子彈，告訴下一個人，最後一個人把子彈的總數傳給上一個人。
每個士兵的代號跟擁有的子彈數是一致。
士兵代號1，有1個子彈。
士兵代號2，有2個子彈。
士兵代號3，有3個子彈。
.
.
.
士兵代號9，有9個子彈。
士兵代號10，有10個子彈。
1
2
3
4
5
6
int func1(士兵代號,士兵子彈數,前面的人的子彈數) {
//判斷前面的士兵是否為最後一個人
//若前面的士兵為最後一個人
if(士兵代號 > 10) 傳回全部子彈數給上一個人
return func1(告訴下一個士兵, 下一個士兵子彈數, 前面的人的子彈數 + 自已的子彈數);
}
1
2
3
4
5
6
7
8
9
10
11
int func1(int i, int bullet, int total) {
//判斷前面的士兵是否為最後一個人
if(i > 10) return total;
total = total + bullet;
return func1(i + 1, bullet + 1, total);
}
int main() {
int total = func1(1, 1, 0);
cout << total << endl;
return 0;
}
55
傳遞函式後處理
士兵長對10個士兵說，告訴最後一個人把子彈數傳上來，後面傳上來的同時也加上自己的子彈數。
每個士兵的代號跟擁有的子彈數是一致。
士兵代號1，有1個子彈。
士兵代號2，有2個子彈。
士兵代號3，有3個子彈。
.
.
.
士兵代號9，有9個子彈。
士兵代號10，有10個子彈。
1
2
3
4
5
6
int func1(士兵代號,士兵子彈數) {
//判斷前面的士兵是否為最後一個人
if(士兵代號 > 10) return 0;//第11個士兵不存在，沒有子彈
//自己的子彈數 + 後面的人的子彈數
return 士兵自己的子彈數 + func1(告訴下一個士兵, 下一個士兵子彈數);
}
1
2
3
4
5
int func1(int i, int bullet) {
if(i > 10) return 0;
//自己的子彈數 + 後面的人的子彈數
return bullet + func1(i+1, bullet+1);
}
55
類別與遞迴
若在類別中寫遞迴函式，參數不用傳遞，可直接使用成員屬性供遞迴使用，成員屬性可以保存值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Story {
public:
int times = 0;
void tell() {
if(times > 10) return;
cout << "第" << times << "次:";
cout << "從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？" << endl;
times++;
tell();
}
};
int main() {
Story story;
story.tell();
return 0;
}
第0次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第1次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第2次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第3次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第4次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第5次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第6次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第7次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第8次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第9次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？
第10次:從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？