遞歸，迴圈，尾遞歸

概念

方法遞歸，簡而言之就是方法本身自己調用自己；

咬文嚼字的分析就是兩個過程：“遞“過程和”歸“過程，所有的遞歸問題都能用地推公式標識.例如斐波拉契數列就能用遞推公式表示：
$$
f(n) = f(n-1) +f(n-2)其中fn(0)=1,f(1)=1
$$
轉換成代碼就是

public static int FibonacciRecursively(int n){
    if(n<2) return n;
    return FibonacciRecursively(n-1) + FibonacciRecursively(n-2);
}

遞歸問題要滿足三個條件：

• 一個問題可以分解成多個子問題的解；子問題就是規模更小的問題（邏輯不變）
• 這些被分解的子問題，除了規模不一樣之外，解決思路一樣
• 存在條件來終止遞歸；這個好理解，因為自己調用自己總不能無線迴圈下去，所以必須有終止條件。

我們來切換一個思考場景：假如這裡有N(>1)個臺階，人上臺階每次只能跨一個或者兩個，那麼有多少種走法能到頂上呢？

我們先分解問題，第一個臺階的走法只有兩種，第一種是走一個臺階，第二種是走兩個臺階；那麼n個臺階的走法就是等於先走1階後，n-1個臺階的走法加上先走2階後，n-2個臺階的走法；

所以用公式表示就是
$$
f(n) = f(n-1)+f(n-2)
$$
滿足終止條件的就是當只有一個臺階的時候就只有一種可能那就是f(1)=1，f(2)=2

所以這個時候就很容易看出這種走樓梯的思想也是斐波拉契數列的體現。

遞歸的陷阱

線程在執行方法的時候，都會分配一定尺寸的棧空間。方法調用時，其中的成員信息（臨時變數，參數，返回地址等）等信息都會存儲線上程棧里，所以這些信息沒有及時被GC，返回大深度的迴圈調用方法，這些記憶體累加起來就會超出該線程分配的棧空間了，自然就報記憶體超出的錯誤。

如何避免記憶體超出這個問題

1. 固定方法調用的深度；當超出設定的深度時，顯示報異常，這種方法局限性很大，總有不滿足這個深度值的時候，這個方法就不奏效了。
2. 把方法改成非遞歸模式（while,for迴圈）這樣就不會存在棧記憶體堆積
3. 在2的基礎之上改寫成“尾遞歸”形式（函數式編程思想）

具體實現方法在後面拓展會具體講到。

遞歸代碼所產生的重覆計算

從走臺階的遞推公式我們發現，其實有很多值被重覆計算了多次。例如計算f(5)，需要先計算f(4)和f(3)，而計算f(4)要計算f(3)和f(2)。其中f(3)就被重覆計算了，那麼為了避免這種情況，縮減重覆計算帶來的時間損耗，我們可以用一個對象結構（散列表等）來記錄已經計算的值，我們就可以避免這個問題了

上述代碼改成如下：

public static int FibonacciRecurisivelyAvoidRepeat (int n) {
    if (n < 2) return n;
    if (dic.ContainsKey (n)) return dic[n];
    int ret = FabonacciRecurisively (n - 1) + FabonacciRecurisively (n - 2);
    dic.Add (n, ret);
    return ret;
}

這種方式是典型的“空間換時間”，並且空間複雜度是O(n)。

遞歸函數拓展理解

在前面談如何避免記憶體超出這個問題時，就談到了可以把遞歸模式的方式改成一個方法中的迴圈體模式

那是不是所有的遞歸方法都能改成這樣呢？答案是可以這麼說。

那麼我們把 f(n)=f(n-1)+f(n-2) 改成非遞歸形式是什麼樣子的呢？請看代碼

public static int FibonacciGeneral(n){  
    if(n < 2) return n;
    int acc1 = 0;   //prevprev
    int acc2 = 1;   //prev
    while(n != 0){
        acc2 = acc1 + acc2;
        acc1 = acc2 - acc1;
        n--;
    }
    return acc1
}

這裡while迴圈是關鍵，主要是實現以下過程

f(5) = f(4) + f(3)

f(5) = [(f(3) + f(2))] + [(f(2) + f(1))]

f(5) = [((f(2) + f(1) )+ f(2))] + [(f(2) + f(1))] f(1) = 1,f(0) =0 或者 f(1) = 1,f(2) = 1,n>2

f(5) = [(((f(1) + f(0)) + f(1))) + (f(1) + f(0))] + [((f(1) + f(0)) + f(1))]

我們可以這麼理解，f(5)是要求的當前值，所以上述公式改成文字公式則為：

f(4)當前值 = f(3)上一個值 + f(2)上上一個值

(f5)當前值 = (f4)上一個值 + (f3)上上一個值

(f6)當前值 = f(5)上一個值 + f(4)上上一個值

..

上一個值 = 求上一個值時參與的上一個值 + 求上一個值時參與的上上一個值

...

所以我們只需要迴圈把單次迴圈體計算的值記錄下來參與下一次迴圈體計算。如此反覆達到結束條件即可，這樣就不會存在棧空間堆積超出記憶體異常了。

我還講了最後一點，是在迴圈遍歷基礎上改寫成的一種尾遞歸方法調用，改寫方式很簡單，把這個方法所用到的變數提取出來當參數使用，就變成下麵的方法

public static int FibonacciTailRecurisively(int n, int acc1, int acc2){
    if(n == 0) return acc1;
    return FibonacciTailRecurisively(n - 1, acc2, acc1 + acc2)
}

這種形式的調用方式就是尾遞歸，在方法最後被調用時，線程棧裡面的臨時變數與參數此時已經沒任何用了，可以被GC回收，所以理論上就是同上面的迴圈方法是一致的，無論有多深，都不會發生記憶體異常。

練習

結合業務場景給定一個菜單結構數據源，如何查找某個菜單的最大父菜單？

普通方法，遞歸，尾遞歸。