Ch12 副函式與遞迴

# Ch12 副函式與遞迴 > 搭配[green judge解題系統](http://www.tcgs.tc.edu.tw:1218/) > Special thanks to [台中女中sagit老師](http://www.tcgs.tc.edu.tw/~sagit/index.htm) \<\(\_ \_\)\> ## > 上一章：[大數運算](https://hackmd.io/s/r1KtmuMdf) > 下一章：[排序](https://hackmd.io/s/ry9twDVpW) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## 什麼是函式 函式的英文是function 你可以把它想像成一塊有特定功能的程式它不會被寫在main裡面因為main本身也是個函式話不多說直接看這個例子 ```cpp= void say_hello() { cout<<"Hello"<<endl; } ``` 在上面的程式裡我們 **宣告** 了一個函式，取名為say_hello 前面的 **void** 代表它並沒有要算出甚麼答案來(後面會有詳細解釋)；後面的 **小括弧()** ，是用來盛裝 **參數** 的，不過這個例子裡沒有參數；底下大括弧裡包著的 ```cpp cout<<"Hello"<<endl; ``` 就是這個函式的 **定義** 簡而言之這個函式的功能呢就是印出一句"Hello"而已接下來只要把剛才那一塊函式放到main上面我們就可以在main裡面 **呼叫** 它了 ```cpp= void say_hello() { cout<<"Hello"<<endl; } int main() { say_hello(); say_hello(); say_hello(); } ``` 這樣一來，就會在小黑窗上看到三個 Hello 至於為什麼說它是「副函式」呢? 因為main本身也是一個函式!! 你可以看到main跟它的格式是一樣的而main就是一個程式的「主函式」(它都叫main了當然是主角) 相較於它，其他的就是「副」函式囉 ## 關於函式的小括弧 上一段有提到 **小括弧()** 是用來盛裝 **參數** 的至於什麼是參數可以看看以下的例子 ```cpp= 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參數 ```cpp= 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 ```cpp= int add3(int x) { int answer = x+3; return answer; } int main() { int Q = 5; int P = add3(Q); cout <也就是要寫個**return** 加上答案 在main裡面呼叫add3這個函式時將Q傳進去並且把add3回傳的結果儲存在P裡面由於Q是5 所以add3回傳的答案會是8 因此在cout<<P之後我們會在小黑窗上看到一個數字8 當然也可以傳兩個以上的變數進去不過回傳只能回傳一個以下示範將兩數字相加的函式 ```cpp= int add(x, y) { int ans = x+y; return ans; } int main() { int a, b; cin >> a; cin >> b; cout << add(a, b); } ``` 它的本質上會和下面這個是一樣的 ```cpp= int main() { int a, b; cin >> a; cin >> b; cout << a+b; } ``` 要練習使用函式我們來複習很久以前寫過的題目：輸入H與W，輸出H\*W 以前是直接在main裡面算答案現在練習看看把運算的過程包到別的函式裡讓main來呼叫它就好 > 【學生練習題】 > - [ ] [Green Judge a005: 矩形面積 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=a005) 函式裡面當然不是只能傻傻地做加減乘除我們以往學過的條件判斷、迴圈等等在函式內都能寫簡而言之函式裡面一切都可以正常寫程式 【例題】 > 輸入一個數字N > 如果N為1，那就印出1 > 否則，如果N是奇數，那就印出3N+1 > 否則，如果N是偶數，那就印出N/2 ```cpp= 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 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=a023) 總之如果函式的功能是拿來算出答案的就必須要在最前面寫上要算的答案的形態該是int就是int 該是string就是string...等等且函式的最後面要記得寫return 加上答案如果沒有要算出答案就在最開頭寫void就好並且最後不需return答案 ## 關於函式的特別性質 猜猜看，執行以下的程式時，會跑出甚麼 ```cpp= 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裡面呼叫函式但其實函式裡面也可以呼叫函式喔像這樣 ```cpp= 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呼叫被別的函式呼叫也可以那麼在自己裡面呼叫自己可以嗎!? 像是這樣 ```cpp= void sayHi() { cout<<"Hi"; sayHi(); } ``` 當然可以喔!! 雖然有點不直覺但是一旦熟悉之後可以用它來達成很多神奇的事情他就是 - - 接下來要介紹的 **遞迴** ## 遞迴的概念 呼叫副函式就像做夢一樣又因為副函式的內容是定義好的所以你可以把它想成套路固定的夢每次作夢的時候帶一些物品進去(參數) 夢醒後會帶回一個答案(回傳) 而遞迴就像是夢中夢你已經帶著物品到了夢中在夢中的套路卻還要再做個夢在程式中的寫法就是讓函式裡面有「自己呼叫自己」的橋段像是這樣 ```cpp= void sayhello() { cout << "hello" << endl; sayhello(); } ``` 這個函式印出一個hello之後會再呼叫自己一次就像是一個說哈囉的夢在夢中說完哈囉還會躺上床再做一個一模一樣的夢中夢在夢中夢說哈囉然後在夢中夢躺床做夢中夢中夢... 你可能會懷疑夢的套路中都有再做一個夢那不就一直夢中夢下去不會醒來了嗎對沒錯你把這段程式拿去執行 ```cpp= void sayhello() { cout << "hello" << endl; sayhello(); } int main() { sayhello(); } ``` 會發現它一直印hello印個沒完直到程式當掉為止我們必須修改程式讓它在某些條件下才要呼叫自己(夢中做夢) 這樣一來才有醒來的契機至於要甚麼條件呢這也是在程式裡面決定的接下來要示範的程式是「限定夢中夢做到5層就結束」所以它的行為應該要像是夢->夢->夢->夢->夢->醒->醒->醒->醒->醒那怎麼知道5次了沒呢就用傳進來的 **參數** 來記錄吧 ```cpp= 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!的程式可以寫成這樣 ```cpp= 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 它定義都告訴你了那程式就照寫就好囉 ```cpp= 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 ```cpp= 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: 費氏數列 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b022) 這題就是剛才介紹的f和Q兩個函式喔 ## 經典問題：河內塔 ![](https://i.imgur.com/k2SUSDs.png) 圖片來自維基百科這個玩具的玩法是這樣的有三根柱子第一根柱子放滿了圓盤最小的在上面最大的在下面想要每次移動一個圓盤來把所有的圓盤都移到第3根柱子上其中移動的過程中每次只能拿一個且絕對不能有大圓盤蓋在小圓盤上的情況發生由於為了讓大圓盤不蓋在小圓盤上會需要有第2根柱子來當成中繼站例如可以把小圓盤先放在中繼站把大圓盤放到目的地後在把小圓盤疊到目的地上這樣一來就可以移動這兩個大小圓盤又可以不會讓大的蓋小的搬的步驟由你來設計但希望讓步驟最少給你圓盤的總量請你印出移動的步驟例如當圓盤的總量是2時印出 Ring 1 from 1 to 2 Ring 2 from 1 to 3 Ring 1 from 2 to 3 意思是先把一號圓盤(最小的圓盤)搬到中繼站再把二號圓盤(最大的圓盤)搬到目的地最後再把一號圓盤從中繼站搬到目的地雖然看起來很簡單但n大起來時會變非常複雜喔像是這個圖片是n為3時的解答但它怎麼知道該這樣做呢? 當然是程式拉 ![](https://i.imgur.com/y3s3sNO.png) (取自家象) 「將3個盤子從A移到C」可以想成「將上面2個盤子用『不知名神奇方法』從A移到B」「將第3個盤子直接從A移到C」「將上面2個盤子用『不知名神奇方法』從B移到C」我不需要知道上面2個盤子是怎麼移的我只需要相信它會神奇的幫我移好所以我要做的事情是 1. 呼叫自己函式，把第1至第n-1個盤子從起點移到中繼站 2. 手動移動第n個盤子，從起點到終點 3. 呼叫自己函式，把第1至第n-1個盤子從中繼站移到終點還要考慮最邊界的條件：當然如果盤子只有一個那直接移到目的地就好其中哪根柱子是起點、哪根是目的地、哪根是中繼站也要從參數傳個仔細，來填填看吧 ```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, ___, ___, ___); } ``` > 【學生練習題】 > - [ ] [Green Judge b023: 河內塔 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b023) 盡量不要複製變填充題自己寫更有意思哦！ ## > 上一章：[大數運算](https://hackmd.io/s/r1KtmuMdf) > 下一章：[排序](https://hackmd.io/s/ry9twDVpW) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)