0%

0-10 遞迴

遞迴是什麼

狹義的遞迴,指的是一個函式,在運行過程中,直接或間接的去呼叫了自己這個函式。沒錯,這是可以的,且是許多演算法實作過程的一部分。

但其實,遞迴不僅僅是語法,而是一種概念。將一個問題,歸約到一個或多個規模較小的子問題,不管它的實作方式是使用遞迴還是迴圈,我認為都可以算是遞迴的一部份。遞迴的這個概念,在演算法競賽裡非常重要。未來在第二、三章節,會一次又一次的,以不同模樣出現,DP根本就是遞迴,排序、資料結構在實作的過程中,亦有許多遞迴的影子。

但現在,我們就來看看狹義遞迴的語法吧

語法

1
2
3
4
void func(){
//...
func();
}

基本上,概念是這樣的。當然,如果沒有自己設定,遞迴是不可能停下來的。由於非常容易掛掉以及 debug 較為困難,因此遞迴成為了不少人的惡夢。

在撰寫遞迴程式時,務必再三確認是否有設定中止條件,以及其是否正確,不然要是停不下來的話就糟糕了。

範例

今天,我要印出從 1 ~ n 裡的每一個整數。當然,我可以使用迴圈實作,而且迴圈也是更好的作法。但為了使讀者更明白遞迴的過程,這裡使用遞迴撰寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
cout << x << '\n';
if(x == n) return; // 中止條件 相當重要
print(x + 1);
}

int main(){
print(1);
}

問題相對直觀,得到參數 x 後,輸出它,並且以 x + 1 作為參數呼叫下一次遞迴,直到 x 等於 5 時才停下。輸出為:

1
2
3
4
5
1
2
3
4
5

但如果今天程式是這樣呢?

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
if(x < n) print(x + 1);
cout << x << '\n';
}

int main(){
print(1);
}

這時候,變成我先呼叫 print(x + 1)後,再輸出 x,這樣的輸出會是什麼呢?稍微有點難想,但若從 5 反推回來,print(5)只輸出 5,print(4) 是 print(5) 後輸出 4,print(3) 是 print(4) 後輸出 3,可以發現,輸出應該就是:

1
2
3
4
5
5
4
3
2
1

困難的來了,如果我的程式是這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
if(x < n){
print(x + 1);
print(x + 2);
}
cout << x << '\n';
}

int main(){
print(1);
}

這就不是個簡單的遞迴函式了,事實上,我也無法在不借助紙筆的方式下,得知它的輸出。呼叫 print(1) 時,我先呼叫了 print(2),這時 print(2) 會一直遞迴下去,直到 print(2) 完全結束以後,再呼叫 print(3)。等到 print(3) 結束後,最後輸出 1。

最後的輸出長這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5
6
4
5
3
5
6
4
2
5
6
4
5
3
1

很難理解吧!我們嘗試透過一些輔助的文字去幫助理解,紀錄一個值d,代表我現在處於遞迴中的第d層,輸出該數前,我先輸出d個空格,以此區分不同層的輸出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x, int d){
if(x < n){
print(x + 1, d + 1);
print(x + 2, d + 1);
}
for(int i=0;i<d;i++) cout<<" ";
cout << x << '\n';
}

int main(){
print(1, 0);
}

輸出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    5
6
4
5
3
5
6
4
2
5
6
4
5
3
1

恩…還是有點難懂,不然我們在呼叫print(x+1)跟print(x+2)時,都輸出一句話好了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x, int d){
if(x < n){
for(int i=0;i<d;i++) cout<<" ";
cout<<"x = " << x <<", print(x+1):\n";
print(x + 1, d + 1);
for(int i=0;i<d;i++) cout<<" ";
cout<<"x = " << x <<", print(x+2):\n";
print(x + 2, d + 1);
}
for(int i=0;i<d;i++) cout<<" ";
cout << x << '\n';
}

int main(){
print(1, 0);
}

輸出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
x = 1, print(x+1): // a
x = 2, print(x+1): // b
x = 3, print(x+1): // c
x = 4, print(x+1): // d
5
x = 4, print(x+2): // d
6
4
x = 3, print(x+2): // c
5
3
x = 2, print(x+2): // b
x = 4, print(x+1):
5
x = 4, print(x+2):
6
4
2
x = 1, print(x+2): // a
x = 3, print(x+1):
x = 4, print(x+1):
5
x = 4, print(x+2):
6
4
x = 3, print(x+2):
5
3
1

其中,// 後方的字相同者,表示其分別是同一層中的 print(x+1) 與 print(x+2) 兩個函式,不是程式實際輸出。

遞迴的思考相當抽象,建議搭配影片理解。

但也因為這樣,遞迴可以用來解一般正常思考下想不到或難解決的問題,下方練習題皆為遞迴經典題,具有相當的難度,但理解後,會發現,用遞迴寫,原來這麼簡潔、乾淨、漂亮!

遞迴是…

我覺得,解決遞迴問題的過程,就像是人生。未來過於遙遠,無法想像、無法預測,我們唯一能夠改變的,只有每個當下的自己。不需要去猜測未來到底會變得如何,我們所能做的一切,只是把握此時此刻,努力面對並解決今天遇到的問題。並且相信:明天一定會更好的!

唯一不同的是,人生會在執行到一半時,突然發生大量意外,但程式基本上不會,除非你寫爛了。

練習題

河內塔問題(易 建議完全了解此題):
ZeroJudge a227

合成函數:(中偏難) : tcirc d002

約瑟夫問題 定時K彈(難 有興趣可寫):ZeroJudge c296

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// ZeroJudge a227
#include<bits/stdc++.h>
using namespace std;

int n;

void hanoi(int n, char from, char to, char mid){
if(n == 1){ // 遞迴停止條件即為只需移一個盤子
cout<< "Move ring " << n << " from " << from << " to " << to << '\n';
return;
}
hanoi(n-1, from, mid, to); // 先想辦法把前面 n-1 個搬到中間那根柱子
cout<< "Move ring " << n << " from " << from << " to " << to << '\n';
hanoi(n-1, mid, to, from); // 把前面 n-1 個柱子從中間搬到目標上
}

int main(){
while(cin>>n){
hanoi(n,'A','C','B');
cout<<'\n';
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 合成函數
#include<bits/stdc++.h>
#define ll long long // 將程式裡的 ll 視為 long long 的意思
using namespace std;

ll n;
string s;

ll str_to_int(string s){ // 將字串轉為整數
ll ans = 0, st = 0;
bool neg = 0;
if(s[st] == '-') neg = 1, st++;
for(int i=st;i<s.size();i++) ans = ans * 10 + s[i] - '0';
if(neg) ans = -ans;
return ans;
}

ll solve(){
cin >> s; // 讀入下一個
if(s == "f"){
ll x = solve(); // f 後面 有 1 個參數
return x * 2 - 3;
}
else if(s == "g"){
ll x = solve(); // g 後面 有 2 個參數
ll y = solve();
return x * 2 + y - 7;
}
else if(s == "h"){
ll x = solve(); // h 後面 有 3 個參數
ll y = solve();
ll z = solve();
return 3 * x - 2 * y + z;
}
else return str_to_int(s); // 是數字的話 就直接回傳
}

int main(){
cout<<solve()<<'\n';
}

定時K彈詳解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定時K彈 最短的最難 https://www.facebook.com/nthuioncamp/posts/438261166736061
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, K;

int solve(int N, int M, int K){
if(K == 0) return 0;
return (solve(N-1, M, K-1) + M) % N;
}

int main(){
cin >> N >> M >> K;
cout << solve(N, M, K) + 1 << '\n';
}