[計程] 遞迴 I：那些年，我們一起追的遞迴

[iForests (森林)]

　　「遞迴只應天上有，凡人該當用迴圈。」

　　是如此一句浪漫的話語，激起高中幾位朋友追逐遞迴最終奧義的熱情。猶記得當年，
趁著夕陽將影子拉至最長的短暫片刻，在校園操場我們共同用黑影在草地上畫出了象徵青
春與冒險的字樣：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
推 csftwpt5566:5566 友情推
推 anfranion:我看到推文  笑了XDDD
推 godgunman:看這個數列先猜Catalan !! (實際上就是阿..)
推 cocohaha:   5566 資工推
推 ggm5566:    5566 友情推
推 r44:        5566 友情推
推 LoganChien:推！ 「遞迴只應天上有，凡人該當用迴圈」
推 vanillaXleft:機車-.-都不照顧長id       還是推啦
→ LoganChien:最後一題是 2007 年 IOI 選訓初試的題目？
→ LoganChien:(小聲問：可以預告一下遞迴 II 嗎...)
→ iForests:當然是「遞迴 II：魔力遞迴」，講 Cut 和使徒四這樣吧
推 godgunman:那 給我給我
→ iForests:自己去拿吧，我把一切都放在那裡了
→ iForests:好我要回屏東了，魔力遞迴交棒給 godgunman
→ iForests:再多說一點，多唱這首歌就可以體會所謂 Cut 的奧義：
→ iForests:http://tw.youtube.com/watch?v=3OVUSCQwCX8
推 csftwpt5566:這首是 56 經典名曲 The First Cut Is The Deepest 啊
推 LoganChien:那我來寫「當數學歸納法遇上遞迴」好了