Ch12 副函式與遞迴

搭配green judge解題系統
Special thanks to 台中女中sagit老師 <(_ _)>

上一章：大數運算
下一章：排序
回目錄：國立科學園區實驗中學C++程式語言自學講義

什麼是函式

函式的英文是function
你可以把它想像成一塊有特定功能的程式
它不會被寫在main裡面
因為main本身也是個函式

話不多說
直接看這個例子




void say_hello()
{
    cout<<"Hello"<<endl;
}

在上面的程式裡
我們宣告了一個函式，取名為say_hello
前面的 void 代表它並沒有要算出甚麼答案來(後面會有詳細解釋)；
後面的 小括弧() ，是用來盛裝參數的，不過這個例子裡沒有參數；
底下大括弧裡包著的

cout<<"Hello"<<endl;

就是這個函式的定義
簡而言之這個函式的功能呢
就是印出一句"Hello"而已

接下來只要把剛才那一塊函式放到main上面
我們就可以在main裡面呼叫它了











void say_hello()
{
    cout<<"Hello"<<endl;
}

int main()
{
    say_hello();
    say_hello();
    say_hello();
}

這樣一來，就會在小黑窗上看到三個 Hello

至於為什麼說它是「副函式」呢?
因為main本身也是一個函式!!
你可以看到main跟它的格式是一樣的
而main就是一個程式的「主函式」(它都叫main了當然是主角)
相較於它，其他的就是「副」函式囉

關於函式的小括弧

上一段有提到
小括弧() 是用來盛裝參數的
至於什麼是參數
可以看看以下的例子











void OAO(int x)
{
    cout<<x<<endl;
}

int main()
{
    OAO(123);
    OAO(1000);
    OAO(-1);
}

小括弧內的「參數」就是那個int x
程式裡面會用到的x就來自於小括弧裡的x
所以OAO這整個函式的功能就是
「拿一個數字x，並且把這個數字x給印出來」

在main裡面
首先我寫了OAO(123)
那麼OAO這個函式就被我「呼叫」了
並且我在呼叫的時候讓它的x先變成123
所以他就會幫我印出123這個數字
而接下來的OAO(1000)與OAO(-1)也是一樣的
所以你最後會在小黑窗上看到
123
1000
-1

在剛才的例子中，只用了一個參數 x
但其實不管用幾個都可以
要用int或是long long或是double或是string或是各種型態都可以

以下示範兩個int參數











void add(int x, int y)
{
    cout << x+y <<endl;
}

int main()
{
    add(1,2);
    add(4,5);
    add(100,200);
}

add這個函式呢
他有兩個參數
分別是 int x 與 int y
而這個函式的定義則是
把傳入的兩個參數x與y加起來後印出來

在main裡面呼叫函式的時候
就記得要傳兩個參數進小括弧裡
如果只傳一個例如呼叫add(1)
或是傳了三個例如呼叫add(1,2,3)
就會噴錯誤喔

這樣的程式執行起來
會在小黑窗上看到印出的
3
9
300

關於函式的型態與答案

在剛才的例子中
我們函式最前面都是寫 void
它的意思就是說
「這個函式並沒有要回傳什麼答案回來」
你可以看到上面的例子就只是單純印出一些東西而已

接下來要介紹讓函式回傳答案
既然他要回傳答案
那就依照他要回傳答案的型態來把void取代掉

例如我想寫個函式，傳入x之後，讓函式把他加三之後的結果回傳給我
既然要回傳的是整數
那麼我這個函式的型態就是個整數
也就是函是的最一開始我要寫個int












int add3(int x)
{
    int answer = x+3;
    return answer;
}

int main()
{
    int Q = 5;
    int P = add3(Q);
    cout << P << endl;
}

上面那個add3的函式
傳入一個x之後
他會用answer來儲存x+3之後的結果
並且把answer回傳過去
也就是要寫個return 加上答案

在main裡面呼叫add3這個函式時
將Q傳進去
並且把add3回傳的結果儲存在P裡面
由於Q是5
所以add3回傳的答案會是8
因此在cout<<P之後
我們會在小黑窗上看到一個數字8

當然也可以傳兩個以上的變數進去
不過回傳只能回傳一個
以下示範將兩數字相加的函式













int add(x, y)
{
    int ans = x+y;
    return ans;
}

int main()
{
    int a, b;
    cin >> a;
    cin >> b;
    cout << add(a, b);
}

它的本質上會和下面這個是一樣的







int main()
{
    int a, b;
    cin >> a;
    cin >> b;
    cout << a+b;
}

要練習使用函式
我們來複習很久以前寫過的題目：輸入H與W，輸出H*W
以前是直接在main裡面算答案
現在練習看看把運算的過程包到別的函式裡
讓main來呼叫它就好

【學生練習題】

Green Judge a005: 矩形面積

函式裡面當然不是只能傻傻地做加減乘除
我們以往學過的條件判斷、迴圈等等
在函式內都能寫
簡而言之函式裡面一切都可以正常寫程式

【例題】

輸入一個數字N
如果N為1，那就印出1
否則，如果N是奇數，那就印出3N+1
否則，如果N是偶數，那就印出N/2













int f(int N)
{
    if(N==1) return 1;
    else if(N%2==1) return (3*N+1);
    else return N/2;
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);
}

來試試用相同的f函式來解3N+1

【學生練習題】

Green Judge a023: 3N+1

總之
如果函式的功能是拿來算出答案的
就必須要在最前面寫上要算的答案的形態
該是int就是int
該是string就是string…等等
且函式的最後面要記得寫return 加上答案

如果沒有要算出答案
就在最開頭寫void就好
並且最後不需return答案

關於函式的特別性質

猜猜看，執行以下的程式時，會跑出甚麼












void to100(int x)
{
    x=100;
}

int main()
{
    int a=3;
    to100(a);
    cout << a << endl;
}

3?
或是100?

答案是，還是會跑出3喔
因為執行函式時
函式裡面的int x算是自己另外宣告的變數
所以就算把x變成100了
傳進去的數字也不會變成100
所以不用擔心變數傳進函式裡會被改變掉!!

函式的呼叫

前面的範例都是在main裡面呼叫函式
但其實函式裡面也可以呼叫函式喔
像這樣



























void IPass()
{
    cout<<"PASS";
}

void IFail()
{
    cout<<"FAIL";
}

void sayResult(int score)
{
    if(score>=60){
        IPass();
    }
    else{
        IFail();
    }
}

int main()
{
    int score;
    cin >> score;
    sayResult(score);
}

在main裡面呼叫了sayResult
而在sayResult裡面會呼叫IPass或是IFail
總而言之
函式不一定要被main呼叫
被別的函式呼叫也可以

那麼
在自己裡面呼叫自己可以嗎!?
像是這樣





void sayHi()
{
    cout<<"Hi";
    sayHi();
}

當然可以喔!!
雖然有點不直覺
但是一旦熟悉之後可以用它來達成很多神奇的事情
他就是 - - 接下來要介紹的遞迴

遞迴的概念

呼叫副函式就像做夢一樣
又因為副函式的內容是定義好的
所以你可以把它想成套路固定的夢

每次作夢的時候帶一些物品進去(參數)
夢醒後會帶回一個答案(回傳)

而遞迴就像是夢中夢
你已經帶著物品到了夢中
在夢中的套路卻還要再做個夢

在程式中的寫法
就是讓函式裡面有「自己呼叫自己」的橋段
像是這樣





void sayhello()
{
    cout << "hello" << endl;
    sayhello();
}

這個函式印出一個hello之後
會再呼叫自己一次
就像是一個說哈囉的夢
在夢中說完哈囉還會躺上床再做一個一模一樣的夢中夢
在夢中夢說哈囉然後在夢中夢躺床做夢中夢中夢…

你可能會懷疑
夢的套路中都有再做一個夢
那不就一直夢中夢下去不會醒來了嗎

對沒錯
你把這段程式拿去執行










void sayhello()
{
    cout << "hello" << endl;
    sayhello();
}

int main()
{
    sayhello();
}

會發現它一直印hello印個沒完
直到程式當掉為止

我們必須修改程式
讓它在某些條件下才要呼叫自己(夢中做夢)
這樣一來才有醒來的契機

至於要甚麼條件呢
這也是在程式裡面決定的

接下來要示範的程式是「限定夢中夢做到5層就結束」
所以它的行為應該要像是
夢->夢->夢->夢->夢->醒->醒->醒->醒->醒

那怎麼知道5次了沒呢
就用傳進來的參數來記錄吧










void sayhello(int x)
{
    cout << "hello" << endl;
    if(x<5) sayhello(x+1);
}

int main()
{
    sayhello(1);
}

【例題】

輸入一個N
輸出N!

既然想算出N!
假設已經知道(N-1)!是多少了
我們就直接把那個(N-1)!拿去乘以N就是N!

為了算出(N-1)!
只需要呼叫自己一次就好

只要自己的函式內容是對的
就不需要擔心(N-1)!會不會被算錯了

就像每次睡覺(呼叫函式)時
不需要為了夢的內容怎麼運作而操心
只要帶正確的物品進去
並把它回傳的答案接住就好

這個夢要算出N!
那就在這個夢中再做個夢算出(N-1)!
把那個夢中夢的答案拿來乘以N就是我這個夢的答案

但若是N已經是1了
實在沒有必要再利用做夢來算出答案
直接回傳1就好

所以算N!的程式可以寫成這樣





int fac(int N)
{
    if(N==1) return 1;
    else return N*fac(N-1);
}

我不需要知道N!的本質是甚麼
我只需要知道N!和(N-1)!之間的關係就好
也就是算出(N-1)!之後再乘以N就是N!

遞迴也是這樣
我根本不需要知道整個運算怎麼變出來的
我只需要知道怎麼利用我呼叫自己以後回傳的結果就好

經典問題：費波那契數列

【例題】

費波那契數列的定義如下
第0項是0
第1項是1
之後每一項都是他前一項和前兩項的和
例如它的前10項為：0,1,1,2,3,5,8,13,21,34

它定義都告訴你了
那程式就照寫就好囉






int f(int n)
{
    if(n==0) return 0;
    else if(n==1) return 1;
    else return f(n-1)+f(n-2);
}

遞迴的好處在這裡
例如f(5)，我並不需要知道怎麼憑空生出f(5)的答案
我只需要知道它是f(3)+f(4)就好
至於f(3)和f(4)我也無法憑空生出來
反正呼叫自己來算就好
既然既然有把函式的定義寫對
就可以完全相信它回傳的答案會是對的!!

【例題】

輸入一個n
輸出在算出n的費波那契時，總共呼叫了幾次函式
例如n為0或1時，因為沒有夢中夢，所以答案都是1次
n為2時，需要分成n為0和n為1各算一次，再加上自己這次，所以是1+1+1=3
n為3時，需要分成n為1和n為2各算一次，再加上自己這次，所以是1+3+1=5

n若不是0或1，就會是n-1的答案加上n-2的答案，再加上這次的1






int Q(int n)
{
    if(n==0) return 1;
    else if(n==1) return 1;
    else return Q(n-1)+Q(n-2)+1;
}

【學生練習題】

Green Judge b022: 費氏數列

這題就是剛才介紹的f和Q兩個函式喔

經典問題：河內塔

圖片來自維基百科

這個玩具的玩法是這樣的
有三根柱子
第一根柱子放滿了圓盤
最小的在上面最大的在下面
想要每次移動一個圓盤
來把所有的圓盤都移到第3根柱子上
其中移動的過程中每次只能拿一個
且絕對不能有大圓盤蓋在小圓盤上的情況發生

由於為了讓大圓盤不蓋在小圓盤上
會需要有第2根柱子來當成中繼站
例如可以把小圓盤先放在中繼站
把大圓盤放到目的地後
在把小圓盤疊到目的地上
這樣一來就可以移動這兩個大小圓盤
又可以不會讓大的蓋小的

搬的步驟由你來設計
但希望讓步驟最少

給你圓盤的總量
請你印出移動的步驟
例如當圓盤的總量是2時
印出
Ring 1 from 1 to 2
Ring 2 from 1 to 3
Ring 1 from 2 to 3

意思是
先把一號圓盤(最小的圓盤)搬到中繼站
再把二號圓盤(最大的圓盤)搬到目的地
最後再把一號圓盤從中繼站搬到目的地
雖然看起來很簡單
但n大起來時會變非常複雜喔
像是這個圖片是n為3時的解答
但它怎麼知道該這樣做呢?
當然是程式拉

(取自家象)

「將3個盤子從A移到C」
可以想成
「將上面2個盤子用『不知名神奇方法』從A移到B」
「將第3個盤子直接從A移到C」
「將上面2個盤子用『不知名神奇方法』從B移到C」

我不需要知道上面2個盤子是怎麼移的
我只需要相信它會神奇的幫我移好
所以我要做的事情是

呼叫自己函式，把第1至第n-1個盤子從起點移到中繼站
手動移動第n個盤子，從起點到終點
呼叫自己函式，把第1至第n-1個盤子從中繼站移到終點

還要考慮最邊界的條件：
當然如果盤子只有一個
那直接移到目的地就好

其中哪根柱子是起點、哪根是目的地、哪根是中繼站
也要從參數傳個仔細，來填填看吧


















void hanoi(int n, int source, int destination, int temp)
{
    if(n==1){
        cout << "Ring 1 from " << source << " to " << destination << endl;
    }
    else{
        hanoi(n-1, ___, ___, ___);
        cout << "Ring " << n << " from " << source << " to " << destination << endl;
        hanoi(n-1, ___, ___, ___);
    }
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, ___, ___, ___);
}

【學生練習題】

Green Judge b023: 河內塔

盡量不要複製變填充題
自己寫更有意思哦！

上一章：大數運算
下一章：排序
回目錄：國立科學園區實驗中學C++程式語言自學講義

Guest Flores2021/08/10 16:35:55

```cpp= void hanoi(int n, int source, int destination, int temp) { if(n==1){ cout << "Ring 1 from " << source << " to " << destination << endl; } else{ hanoi(n-1, ___, ___, ___); cout << "Ring " << n << " from " << source << " to " << destination << endl; hanoi(n-1, ___, ___, ___); } } int main() { int n; cin >> n; hanoi(n, ___, ___, ___); } ```

destination (Edited)

Guest Hill2022/03/05 09:24:22

```cpp= void to100(int x) { x=100; } int main() { int a=3; to100(a); cout << a << endl; } ```

a (Edited)

Guest Blair2022/03/05 09:24:48

Guest Walton2022/03/05 09:25:15

void to100(int x) { x=100; } int main() { int a=3; to100(a); cout << a << endl; } (Edited)

Chu-Ling Ko

2022/05/17 01:20:34

謝謝！ (Edited)

2022/05/17 01:21:26