資料結構與算法-遞歸

1.什麼是遞歸

　舉一個例子：大學軍訓的時候，一個隊伍，開頭的人A想知道這個隊伍一共有多少人，但是每個人隻能通過旁邊的交流，那如何統計呢？

    我們可以先找出最後一個人，A可以問旁邊的人B是否為最後一個人，B又問下一個人，如此類推，等到了最後一個人，再将号碼傳回到第一個人A，每往前一個，号碼上就+1，第一個人A就知道這個隊伍有多少人了。

    公式：g(n)=g(n-1)+1;g(1)=1

int AskNumberOfTeams(int n) {
    if(n == 1) {
        return 1;
    }
    return 1 + AskNumberOfTeams(n-1);
}      

　　遞歸可以看成一個嵌套的形式，一層層嵌套，執行相同的内容，到終止條件後往上傳回結果。

　　遞歸有三個要素：1.判斷問題能否才分成小問題；2.每個小問題解決方案是否一緻；3.是否有終止條件

2.簡單應用

　　斐波拉契數列

　　　　斐波拉契數列指的是1、1、2、3、5、8、13、21、34、55……。我們根據數列可以推導出，目前n位置的數值可以從前兩個數值和得到，公式為f(n)=f(n-1)+f(n-2)，f(1)=1與f(2)=1這兩個是遞歸的終止條件。　　

int CalFibonacci(int n) {
    if(n == 1 || n == 2) {
        return 1;
    }
    return CalFibonacci(n-1) + CalFibonacci(n - 2);
}      

 　　階乘

       　　階乘n!是小于等于n的正整數的積，并且0!=1，n!=1*2*3*4*……*(n-2)*(n-1)*n。根據公式可以拆分成n!=(n-1)!*n，且終止條件為0!=1。

int CalFactorial(int n) {
    if(n == 0) {
        return 1;
    }
    return CalFactorial(n - 1) * n;
}      

3.遞歸寫成非遞歸的形式

    遞歸的形式都是可以寫成非遞歸的形式，用循環來替代遞歸。以上上面兩個應用可以改寫成：

    斐波拉契數列

int CalFibonacciCycle(int n) {
    if(n == 1 || n == 2) {
        return 1;
    }
    int SecondValue = 1;//f(n-2)
    int FirstValue = 1;//f(n-1)
    int resultvalue;//f(n)
    for(int i=3; i<=n; i++) {
        resultvalue = FirstValue + SecondValue;
        SecondValue = FirstValue;
        FirstValue = resultvalue;
    }
    return resultvalue;
}      

　　階乘

int CalFactorialCycle(int n) {
    if(n == 0) {
        return 1;
    }
    int FirstValue = 1;//f(n-1)
    int resultvalue;//f(n)
    for(int i=1; i<=n; i++) {
        resultvalue = i * FirstValue;
        FirstValue = resultvalue;
    }
    return resultvalue;
}