「遞迴只應天上有，凡人該當用迴圈。」 　　是如此一句浪漫的話語，激起高中幾位朋友追逐遞迴最終奧義的熱情。猶記得當年， 趁著夕陽將影子拉至最長的短暫片刻，在校園操場我們共同用黑影在草地上畫出了象徵青 春與冒險的字樣：Recursion。（故事後來寫成小說，詳見維基 http://0rz.tw/0a4Yf） 　　再說下去就太拖戲了。 　　　　　　　　　　　　　　　　　　－ 　　首先先來談函式，一個特定的函式用來解決特定的問題。像是以下函數的功能即為讀 入兩個整數 a 和 b，將兩者相加後再減去兩者兩減，並回傳給呼叫他的人： int fun1(int a,int b){ return (a+b)-(a-b); } main(){ int c; c=fun1(38,19); } 結束後 c 的值為 38。當然啦，函數非常的有用，再多舉幾個請自行判斷其用途： int fun2(int a,int b){ int fun3(int x){ void fun4(int num){ if(a>b) if(x>0) printf("Hello, I'm "); return a; return x; printf("%d ",num); return b; return -x; printf("years old."); } } } 　　　　　　　　　　　　　　　　　　－ 　　遞迴則是在函數尚未結束之前，又在函數內部呼叫了函數自己。原則上遞迴用來解決 結構類似的問題，許多情況下也可以看作把一個大問題切割成許多小問題並分別解決。 　　直接看例子幫助了解，拿最簡單的來講，要計算 1+2+3+...+n 的值。 方法一（迴圈）： #include <cstdio> #include <cstdlib> main(){ int n,sum,i; scanf("%d",&n); sum=0; for(i=1;i<=n;i++) sum+=i; printf("sum=%d\n",sum); system("PAUSE"); } 方法二（遞迴）： 　　先來觀察我們的問題，要求的東西是從 1 累加到 n 的值。因此可以定義一個函式， 用來計算我們要的答案（即 1+2+...+n），而影響這個函式的是究竟要加到多少才停止， 也就是輸入中的 n，於是我們傳入函數的參數為 n。 int calc(int n){ //不會寫... } 再來，考慮要如何解決 1+2+...+n 的問題。 { 1+2+3+...+(n-1)+n } = { 1+2+3+...+(n-1) } + n 原諒我的表達能力。我的意思是，要求 1 加到 n，我們可以先算出 1 加到 n-1 的 值，最後再多加一個 n 就是答案了，因此函式為： int calc(int n){ int ans; //先用 calc(n-1) 算出 1+...+n-1，最後再加 n ans=calc(n-1)+n; //在這裡你可以假設 calc(n-1) 會正確算出結果 return ans; //回傳答案 } 還沒結束，得再繼續努力。試試看計算 1+2+3 會發生什麼事： calc(3) = calc(2)+3 = calc(1)+2+3 = calc(0)+1+2+3 = calc(-1)+1+2+3 = ... 遞迴不會結束！這裡帶出了遞迴非常重要的一件事情，那就是結束條件。加總問題的 結束條件其實很容易，即當 n = 1 時代表 1+...+1 答案為 1，這樣遞迴就完成了。 #include <cstdio> #include <cstdlib> int calc(int n){ if(n==1) return 1; return calc(n-1)+n; } main(){ int n,sum; scanf("%d",&n); printf("sum=%d\n",calc(n)); system("PAUSE"); } 故事告訴我們，遞迴有兩件非常重要的事情： ‧遞迴式 ：本例中 f(n) = f(n-1) + n ‧結束條件：本例中 f(n) = 1，當 n = 1 事實上，只要能寫出遞迴式和結束條件，要寫好遞迴函數就不是件困難的事情。國中 或高中時有個有名的數列叫 Fibonacci 數列，接下來以此為例： ‧遞迴式 ：fib(n) = fib(n-1) + fib(n-2) ‧結束條件：fib(1) = fib(2) = 1 寫完兩大要素後，馬上就能完成相對應的 code（請別輸入太大的 n）： #include <cstdio> #include <cstdlib> int fib(int n){ if(n==1 || n==2) //這裡是結束條件 return 1; return fib(n-1)+fib(n-2); //這裡是遞迴式 } main(){ int n; scanf("%d",&n); printf("The n-th Fibonacci number is %d\n",fib(n)); system("PAUSE"); } 甚至求組合數也是輕而易舉： ‧遞迴式 ：C(n,k) = C(n-1,k) + C(n-1,k-1) ‧結束條件：C(n,k) = 0，當 n < k C(1,k) = 1 C(n,0) = 1 #include <cstdio> #include <cstdlib> int Combi(int n,int k){ if(n<k) return 0; if(n==1 || k==0) return 1; return Combi(n-1,k)+Combi(n-1,k-1); } main(){ int n,k; scanf("%d %d",&n,&k); printf("C(%d,%d) = %d\n",n,k,Combi(n,k)); system("PAUSE"); } 　　　　　　　　　　　　　　　　　　－ 最後再強調一次，遞迴通常用來解決結構相似的問題。而遞迴確實是比較不容易了解 的概念，多試幾次，並拿不同的東西寫寫看（例如求階乘）或許就能夠體會了。 實際練習一題不簡單但也不會太難的問題。答案下一篇再講，休息一下。 Question：將一正 n 邊形分割成 n-2 個三角形，有幾種分割方法？ Sample Input Sample Output 4 2 分割方法見圖： 5 5 6 14 http://0rz.tw/cb4TF 7 42 8 132 9 429 10 ???? -- 沒有仔細校稿也沒有套色，請多見諒。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.242.109