遞迴(C++)

遞迴也是一種暴力演算法，可以走訪所有狀態，找出答案。在撰寫遞迴函式前，先要了解如何自訂函式。

(1)自訂函式

函式用於結構化程式，將相同功能的程式獨立出來，經由函式的呼叫，傳入資料與回傳處理後的結果，程式設計師只要將函式寫好，可以不斷利用此函式做相同動作，可以達成程式碼不重複，要修改此功能，只要更改此函式。

函式的定義、傳回值與呼叫

自訂函式需要包含三個部分，分別是函式的宣告、函式的定義與函式的呼叫。函式的宣告用於告訴主程式(main)或其他函式有此自訂函式可以使用；函式的定義是實作函式的功能，輸入參數與回傳處理後的結果；函式的呼叫於主程式(main)或其他函式呼叫自訂函式，讓自訂函式真正執行。

(1-1)函式的宣告

函式在主程式(main)前要進行宣告，函式宣告只要指出函式的名稱、參數個數、參數的資料型別與函式回傳資料型別，宣告語法如下。

回傳資料型別 函式名稱( 參數1的資料型別 , 參數2的資料型別 , …)

(1-2)函式的定義與傳回值

以下為函式的定義，函式名稱後接著一對小括號，小括號可以填入要傳入函式的參數，當參數有多個的時候以逗號隔開，函式名稱前面宣告函式回傳的資料型別，函式的範圍為函式名稱後使用一對大括號所包夾起來的範圍，當函式需要傳回值使用指令return，表示程式執行的控制權由函式轉換為原呼叫函式，函式的定義與傳回值格式，如下。

函式定義與傳回值的語法

回傳資料型別 函式名稱(參數1的資料型別 參數1, 參數2的資料型別 參數2 , …){

                 區域變數的宣告 

                 函式的敘述區塊 

                return 要傳回的變數或值; 

}

(1-3)函式的呼叫

程式經由函式呼叫，將資料傳入函式，函式處理後傳回結果給呼叫程式

方法一：無傳回值的呼叫語法，於主程式(main)或其他函式中利用函式名稱與參數來呼叫函式。

函式名稱(參數值1,參數值2,…)

方法二：有傳回值的呼叫語法，等號右邊要先做完，利用函式名稱與參數來呼叫函式，最後函式回傳值給變數，變數就紀錄函式呼叫後的回傳值。

 變數=函式名稱(參數值1,參數值2,…)

(2)遞迴

遞迴是有趣的程式設計技巧，函式執行過程中呼叫自己，稱作遞迴。而這樣的自己呼叫自己，需要有終止的條件，若沒有終止的條件就會形成無窮遞迴。

(2-1)求解n階乘（n!）

數學上定義n階乘為「n!=n*(n-1)*(n-2)*(n-3)*…*3*2*1」。我們可以分階段看，求解n階乘，可以分解成n乘以(n-1)階乘意即「n!=n*(n-1)!」，求解(n-1)階乘，可以分解成n-1乘以(n-2)階乘意即「(n-1)!=(n-1)*(n-2)!」，求解(n-2)階乘，可以分解成n-2乘以(n-3)階乘意即「(n-2)!=(n-2)*(n-3)!」，依此類推，直到求解3階乘，可以分解成3乘以2階乘意即「3!=3*2!」，求解2階乘，可以分解成2乘以1階乘意即「2!=2*1!」，1!就不用再往下求解直接就是1，這樣一層一層遞迴下去直到求解1!，就終止遞迴，再一層一層往上回推，如下圖。

寫成遞迴函式，假設函式名稱為f(n)為求解n!，f(n-1)為求解(n-1)!，代入上圖。

(2-2)m的n次方

求解m的n次方之值，數學上定義m的n次方為n個m相乘。我們可以分階段看，求解m的n次方，可以分解成m乘以m的n-1次方意即「m^n=m*m^(n-1)」，求解m的n-1次方，可以分解成m乘以m的n-2次方意即「m^(n-1)=m*m^(n-2)，求解m的n-2次方，可以分解成m乘以m的n-3次方意即「m^(n-2)=m*m^(n-3)，依此類推，直到求解m的3次方，可以分解成m乘以m的2次方意即「m^3=m*m^2」，m的2次方，可以分解成m乘以m的1次方意即「m^2=m*m^1」，m^1就不用再往下求解直接就是m，這樣一層一層遞迴下去直到求解m^1，就終止遞迴，再一層一層往上回推，如下圖。

寫成遞迴函式，假設函式名稱為p(n)為求解m^n，p(n-1)為求解m^(n-1)，代入上圖。

求解F(4)的過程

(1) 求解F(4)先遞迴呼叫求F(3)。

(2) 求解F(3)先遞迴呼叫求F(2)。

(3) 求解F(2)先遞迴呼叫求F(1)。

(4) F(1)值為1，所以回傳F(1)，即回傳1。

(5) 求解F(2)，F(1)已經有解，但需要再遞迴呼叫求F(0)。

(6) F(0)值為1，所以回傳F(0)，即回傳1。

(7) 求解F(2)，F(1)與F(0)已經求得，F(2)=F(1)+F(0)=1+1=2，回傳F(2)，即回傳2。

(8) 求解F(3)，F(2)已經有解，但需要再遞迴呼叫求F(1)。

(9) F(1)值為1，所以回傳F(1)，即回傳1。

(10) 求解F(3)，F(2)與F(1)已經求得，F(3)=F(2)+F(1)=2+1=3，回傳F(3)，即回傳3。

(11) 求解F(4)，F(3)已經有解，但需要再遞迴呼叫求F(2)。

(12) 求解F(2)先遞迴呼叫求F(1)。

(13) F(1)值為1，所以回傳F(1)，即回傳1。

(14) 求解F(2)，F(1)已經有解，但需要再遞迴呼叫求F(0)。

(15) F(0)值為1，所以回傳F(0)，即回傳1。

(16) 求解F(2)，F(1)與F(0)已經求得，F(2)=F(1)+F(0)=1+1=2，回傳F(2)，即回傳2。

求解F(4)，F(3)與F(2)已經求得，F(4)=F(3)+F(2)=3+2=5，如此得到結果。

範例練習1  APCS201902第3題函數運算式求值 

https://zerojudge.tw/ShowProblem?problemid=f640

有三個函數：

f(x) = 2x – 3

g(x, y) = 2x +y – 7

h(x, y, z) = 3x – 2y + z

另有一個由這三個函數所組成的運算式，依序給你其中的函數名稱及參數，請求出這個運算式的值。例如：

h f 5 g 3 4 3

代表

h(f(5), g(3, 4), 3)

=h(7, 3, 3)

=18

輸入說明

輸入只有一行，含有運算式中所有的函數名稱及參數值，兩兩以一個空白隔開。函數名稱為 f、g、h 其中一個字母，參數值則為一個介於 -1000 及 1000 的整數。

輸出說明

輸出運算式的值。運算過程及結果的整數值其絕對值均不大於10^9。

輸入範例1

f f f 2

輸出範例1

-5

輸入範例2

h f 5 g 3 4 3

輸出範例2

18

解題策略

運算式+遞迴

範例練習3  APCS201802第3題支點切割 

zerojudge：https://zerojudge.tw/ShowProblem?problemid=f638

輸入一個大小為N的一維整數陣列p[]，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於3或切到給定的層級K就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，但不可以是兩端點，也就是說，若區段的範圍是[s,t]，則要找出切點 m ∈ [s+1,t-1]，使得

越小越好，如果有兩個最佳切點，則選擇編號較小的。所謂切割層級的限制，第一次切以第一層計算。

輸入說明

輸入格式：第 一行 有兩 個正整數 N 與 K 。 第二行 有 N 個正整數 代表陣列內容 p[1] ~ p [N 數字間以空白隔開， 總和不超過 10^9。 N ≤ 50000，切割層級限制K<30。

輸出說明

所有切點的p[ ]值總和。 

輸入範例1

7 1

2 4 1 3 7 6 9

輸出範例1

7

說明

選擇7，將第二層分成左邊[2 4 1 3]與右邊[6,9]， 

左邊為2*(-4)+4*(-3)+1*(-2)+3*(-1)=-25，右邊為9*2+6*1=24，左右兩邊加總為1。

輸入範例2

7 3

2 4 1 3 7 6 9

輸出範例2

11

第一層選擇7，將第二層分成左邊[2 4 1 3]與右邊[6,9]， 

左邊為2*(-4)+4*(-3)+1*(-2)+3*(-1)=-25，右邊為9*2+6*1=24，左右兩邊加總為1。

第二層[2 4 1 3]選擇4或1都是5，4在左邊所以選擇4，左邊[2]右邊[1 3]

左邊2*(-1)=-2，右邊3*2+1*1=7，左右兩邊加總為5。

第二層[6,9]因為個數小於3所以不用處理。

第三層以後都小於3個元素，不用處理。

7+4=11

解題策略

前綴和與後綴和+遞迴 

範例練習4  d544北市賽  98 1-algae  費氏數列  

上傳作業：http://203.68.236.9/problem/b0031

zerojudge連結 http://zerojudge.tw/ShowProblem?problemid=d544

內容 ：

根據最新的生態學研究報導，在台北市植物園的蓮花池中，發現了一種奇特的海藻，此種海藻的外形具有一種十 分特殊的性質：

• 1. 種子落地後，經過一天的時間，會先長出一根長一公分的綠色分枝。

  2. 綠色的分枝，經過一天的時間後，會向上成長一公分，並且變成黃色。

  3. 黃色的分枝，經過一天的時間後，會向上成長一公分，並且分成左右兩個分枝，其中左分枝為綠色，右分枝為黃色。

 所有的分枝都不會互相交錯，同時恰好成長在同一個平面上。

舉例來說，若我們由左而右俯視觀察此海藻每天的生長情形，則在種子落地後的第一天，觀察結果為『綠』，第 二天的觀察結果為『黃』，第三天的觀察結果為『綠黃』，第四天的觀察結果為『黃綠黃』， 第五天的觀察結果為『綠黃黃綠黃』，依此類推。

請寫一個程式，預測在第 N 天時，由左邊數來第 K 個分枝的顏色為何。

輸入說明 ： 

 每個測資點中的第一行有一個正整數 M 代表此測資點中共有 M 組測試資料

 每組測試資料含有兩個以空白相間隔的正整數，分別依次為 N 與 K

 為方便起見，所有的測試資料皆滿足 0 < M < 100，0 < N < 100 且 0 < K < 2000000000

輸出說明 ： 

 每行輸出第 N 天時

 由左邊數來第 K 個分枝的顏色（請用數字 0 代表綠色，1 代表黃色）

 若第 N 天時，此海藻的分枝數少於 K，則輸出 -1

範例輸入 ： 

3

3 1

5 5

6 100 

範例輸出 ：

0

1

-1 

出處 ： 

北市 98 資訊學科能力競賽

解題策略

費氏數列+遞迴