code風景區 (code scenic): 給新手的C++教學 (上冊) - 13

回到「給新手的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;
}