2017年3月2日 星期四

給新手的C++教學 (上冊) - 13 - 16. 函式的遞迴

回到「給新手的C++教學 (上冊)」

回到「13. 額外語法 (Extra syntax)」

上一頁

註: 小莫使用的程式碼上色網站掛掉了,因此本頁的程式碼都沒有顏色,等該網站恢復之後會再進行程式碼上色的動作,暫時造成不便敬請見諒。若您發現該網站已經恢復運作,本頁程式碼卻還沒更新,也歡迎以各種方式提醒小莫哦~ ^_^

遞迴?甚麼是遞迴呢?
其實數學也有遞迴哦~
不知道也沒關係,因為小莫高一學程式的時候也完全沒聽過「遞迴」這個字眼XD
反正就是個專有名詞嘛XD,概念其實不難~

舉個例子,現在小莫創造一個函式$f$,當$n=1$時會回傳$1$,$n=2$時也會回傳$1$:

#include<cstdio>
int f(int n)
{
    if(n==1||n==2) return 1;
    printf("無法處理這個n\n");
    return -1;
}
int main()
{
    printf("f(1)=%d\n",f(1));
    printf("f(2)=%d\n",f(2));
    return 0;
}

那$n=3$呢?小莫想要讓它回傳「$f(1)+f(2)$」
甚麼意思?
$f(1)=1$,$f(2)=1$,所以$f(3)=f(1)+f(2)=1+1=2$啦
也就是當$n=3$時會回傳$2$,只是這個$2$是被計算出來的

那$n=4$呢?小莫想要讓它回傳「$f(2)+f(3)$」
$f(2)=1$,$f(3)=2$,所以$f(4)=f(2)+f(3)=1+2=3$啦
也就是當$n=4$時會回傳$3$,只是這個$3$是被計算出來的

那$n>4$呢?相信您已經猜到了,只要$n>2$,小莫想要讓它回傳的就是$f(n-2)+f(n-1)$!

那$f$這個函式的程式碼要怎麼寫呢?不用怕,電腦學過C++,很聰明的,直接寫出來,看看電腦能不能看懂!


#include<cstdio>
int f(int n)
{
    if(n==1||n==2) return 1;
    if(n>2) return f(n-2)+f(n-1);
    printf("無法處理這個n\n");
    return -1;
}
int main()
{
    printf("f(1)=%d\n",f(1));
    printf("f(2)=%d\n",f(2));
    for(int i=3;i<=10;i++) printf("f(%d)=%d\n",i,f(i));
    return 0;
}
成功執行且結果符合預期!


哈哈,程式執行成功了耶~
驗證一下:
$f(3)=f(1)+f(2)=1+1=2$
$f(4)=f(2)+f(3)=1+2=3$
$f(5)=f(3)+f(4)=2+3=5$
$f(6)=f(4)+f(5)=3+5=8$
$f(7)=f(5)+f(6)=5+8=13$
$f(8)=f(6)+f(7)=8+13=21$
$f(9)=f(7)+f(8)=13+21=34$
$f(10)=f(8)+f(9)=21+34=55$
耶~電腦果然沒讓我們失望!

這就是傳說中的遞迴函式
咦?所以哪裡是遞迴呀?
注意到,在$f$這個函式內,我們呼叫了$f$ (甚麼是呼叫?)
咦?好像哪裡怪怪的,怎麼$f$都還沒執行完就想要再執行$f$呢?
這就是初學者們對遞迴函式常常百思不解的原因
廢話不多說,用動畫解釋最清楚!

Animation


可以發現,雖然程式碼中寫的是「在$f$中呼叫$f$」,但對電腦來說則是「在$f1$中呼叫$f2$」,也就是$f1$和$f2$雖然有一模一樣的邏輯,但執行時是獨立互不影響的兩個函式。當然可以是$f2$依據$f1$的執行結果來設定其內部的變數,但是當$f1$執行時,不管$f1$怎麼修改在它內部宣告的變數,都不會影響到$f2$內部的變數 (可參考動畫中對$n$的說明),除非您利用某些巧妙的技巧硬是要兩個函式之間互相溝通,或是程式出錯XD
當有「函式呼叫函式」的情況發生時,會出現一種「上下函式層層堆疊」的神奇結構,專業上我們用「stack (堆疊)」來稱呼類似這種的神奇結構。如果您有玩過上面的動畫,您應該會發現有時候會出現「函式上下堆疊起來」的現象,然而,只有當下面的函式都執行完畢之後,某函式才會繼續執行
很神奇吧!上面的動畫小莫花了整整兩天的時間製作,儘管玩吧!
(發現bug一定要講哦,不然就前功盡棄了XD)

順帶一提,相信很多讀者也早就知道,小莫剛剛創造的函式$f$其實就是大名鼎鼎的「費波那契數列」啦www
聰明的您可能也會想到,$f$不是用迴圈就能計算出來了嗎?如果想得更仔細的話,使用迴圈的效率甚至比遞迴高很多很多!

那麼,遞迴有甚麼用呢?
遞迴的用處可多著呢!有些事情不使用遞迴就會很麻煩,非常麻煩!
舉個例子:給你$N$,請枚舉$N$階排列!

舉例來說,如果$N=4$,那麼您的答案應該長這樣:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

恩,雖然麻煩,但寫個4層迴圈可以做到!第$i$層迴圈做的事就是枚舉出還沒用過的數字並放在第$i$個位置
那,如果$n=100$呢?難道要寫$100$層迴圈嗎?
哈哈哈,遞迴登場的時刻到了!
請您想想看要怎麼寫吧 ^_^

參考解答:

#include<cstdio>
void f(int n,int i,int *answer,bool *number_used)
{
    if(i==n+1)//已經使用n個數字組出一個長度為n的排列了!
    {
        for(int j=1;j<=n;j++)
        {
            if(j==1) printf("%d",answer[j]);
            else     printf(" %d",answer[j]);
        }
        printf("\n");
        return;
    }
    for(int j=1;j<=n;j++)
    {
        if(!number_used[j])
        {
            answer[i]=j;
            number_used[j]=true;
            f(n,i+1,answer,number_used);
            number_used[j]=false;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int answer[n+1];
    bool number_used[n+1];
    for(int i=1;i<=n;i++)number_used[i]=false;
    f(n,1,answer,number_used);
    return 0;
}

$N=3$時程式的執行結果
$N=4$時程式的執行結果
$N=5$時程式的執行結果

遞迴還可以做到很多事情,例如從質因數分解式枚舉因數,在搜尋資料、圖論上的應用更是不勝枚舉
發揮您的巧思,甚麼事情也可以用遞迴做到呢?:D

下一頁

感謝:
(版權所有 All copyright reserved)

2 則留言:

  1. 放棄上色,選我正解

    回覆刪除
    回覆
    1. 哈哈哈,看來目前只好這樣囉XD
      沒有顏色總比顏色不同調好~

      刪除

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原