之前的文章咱們已經聊過了「 數組和鏈表 」、「 堆棧 」和「 隊列 」，今天咱們來看看「 遞歸 」，當然「 遞歸 」並不是一種數據結構，它是很多算法都使用的一種編程方法。它太普遍了，並且用它來解決問題非常的優雅，但它又不是那麼容易弄懂，所以我特意用一篇文章來介紹它。

一、「 遞歸 」是什麼？

遞歸 就是指函數直接或間接的調用自己，遞歸是基於棧來實現的。遞歸的經典例子就是 斐波拉契數列（Fibonacci）。一般如果能用遞歸來實現的程序，那它也能用循環來實現。用遞歸來實現的話，代碼看起來更清晰一些，但遞歸的性能並不佔優勢，時間複雜度甚至也會更大一些。

上圖為 斐波拉契數列 圖例。

要實現遞歸，必須滿足2個條件：

1. 可調用自己

   就是我們要解決的這個問題，可以通過函數調用自己的方式來解決，即可以通過將大問題分解為子問題，然後子問題再可以分解為子子問題，這樣不停的分解。並且大問題與子問題/子子問題的解決思路是完全一樣的，只不過數據不一樣。因此這些問題都是通過某一個函數去解決的，最終我們看到的就是不停得函數調用自己，然後就把問題化解了。

   如果這個問題不能分解為子問題，或子問題的解決方法與大問題不一樣，那就無法通過遞歸調用來解決。

2. 可停止調用自己

   停止調用的條件非常關鍵，就是大問題不停的一層層分解為小問題後，最終必須有一個條件是來終止這種分解動作的（也就是停止調用自己），做遞歸運算一定要有這個終止條件，否則就會陷入無限循環。

下面還是以 斐波拉契數列（Fibonacci）為例，我們來理解一下遞歸：

斐波拉契數列就是由數字 1，1，2，3，5，8，13…… 組成的這麼一組序列，特點是每位數字都是前面相鄰兩項之和。如果我們希望得出第N位的數字是多少？

1. 可以使用循環的方式求解：

   這裡就不列代碼了，思路是：我們知道最基本的情況是 f(0)=0，f(1)=1，因此我們可以設置一個一個循環，循環從i=2開始，循環N-1次，在循環體內 f(i)=f(i-1)+f(i-2)，直到i=N-1，這樣循環結束的時候就求出了f(N)的值了。

2. 更優雅的方式是使用遞歸的方式求解：

   我們知道斐波拉契數列的邏輯就是：

   

   可以看出，這個邏輯是滿足上面2個基本條件，假如求解 f(3)，那 f(3)=f(2)+f(1)，因此我們得繼續去求解f(2)，而 f(2)=f(1)+f(0)，因此整個求解過程其實就在不斷的分解問題的過程，將大問題f(3)，分解為f(2)和f(1)的問題，以此類推。既然可以分解成子問題，並且子問題的解決方法與大問題一致，因此這個問題是滿足“可調用自己”的遞歸要求。

   同時，我們也知道應該在何時停止調用自己，即當子問題變成了f(0)和f(1)時，就不再需要往下分解了，因此也滿足遞歸中“可停止調用自己”的這個要求。

   所以，斐波拉契數列問題可以採用遞歸的方式去編寫代碼，先看圖：

   

   我們將代碼寫出來：

   int Fb(int n){
      if(n<=1) return n==0?0:1；
      return Fb(n-1)+Fb(n-2); //這裡就是函數自己調用自己
   }
   

   從上面的例子可以看出，我們寫遞歸代碼最重要的就是寫2點：

3. 遞推公式

   上面代碼中，遞推公式就是 Fb(n)=Fb(n-1)+Fb(n-2)，正是這個公式，才可以一步步遞推下去，這也是函數自己調用自己的關鍵點。因此我們在寫遞歸代碼的時候最首先要做的就是思考整個邏輯中的遞推公式。

4. 遞歸停止條件

   上面代碼中的停止條件很明顯就是：if(n<=1) return n==0?0:1；這就是遞歸的出口，想出了遞推公司之後，就要考慮遞歸停止條件是啥，沒有停止條件就會無限循環了，通常遞歸的停止條件是程序的邊界值。

   我們對比實現斐波拉契數列問題的2種方式，可以看出遞歸的方式比循環的方式在程序結構上更簡潔清晰，代碼也更易讀。但遞歸調用的過程中會建立函數副本，創建大量的調用棧，如果遞歸的數據量很大，調用層次很多，就會導致消耗大量的時間和空間，不僅性能較低，甚至會出現堆棧溢出的情況。

   我們在寫遞歸的時候，一定要注意遞歸深度的問題，隨時做好判斷，防止出現堆棧溢出。

   另外，我們在思考遞歸邏輯的時候，沒必要在大腦中將整個遞推邏輯一層層的想透徹，一般人都會繞暈的。大腦很辛苦的，我們應該對它好一點。我們只需要關注當前這一層是否成立即可，至於下一層不用去關注，當前這一層邏輯成立了，下一層肯定也會成立的，最後只需要拿張紙和筆，模擬一些簡單數據代入到公式中去校驗一下遞推公式對不對即可。

二、「 遞歸 」的算法實踐？

我們看看經常涉及到 遞歸 的 算法題（來源leetcode）：

算法題：實現 pow(x, n) ，即計算 x 的 n 次冪函數。

說明:
    -100.0 < x < 100.0
    n 是 32 位有符號整數，其數值範圍是 [−2^31, 2^31 − 1]

示例:
輸入: 2.00000, 10
輸出: 1024.00000

解題思路：

方法一：
暴力解法，直接寫一個循環讓n個x相乘嘛，當然了這種方式就沒啥技術含量了，時間複雜度O(1)，代碼省略了。

方法二：
基於遞歸原理，很容易就找出遞推公式 f(n)=x*f(n-1)，再找出遞歸停止條件即n==0或1的情況就可以了。不過稍微需要注意的是，因為n的取值可以是負數，所以當n小於0的時候，就要取倒數計算。代碼如下：
class Solution {
    public double myPow(double x, int n) {
        if(n==0) return 1;
        if(n==1) return x;
        if(n<0) return 1/(x*myPow(x,Math.abs(n)-1));
        return x*myPow(x,n-1);
    }
}
這個方法其實也有問題，當n的數值過大時，會堆棧溢出的，看來也是不最佳解，繼續往下看。

方法三：
利用分治的思路，將n個x先分成左右兩組，分別求每一組的值，然後再將兩組的值相乘就是總值了。即 x的n次方 等於 x的n/2次方 乘以 x的n/2次方。以此類推，左右兩組其實還可以分別各自繼續往下分組，就是一個遞推思想了。但是這裡需要考慮一下當n是奇數的情況，做一個特殊處理即可，代碼如下：
class Solution {
    public double myPow(double x, int n) {
        //如果n是負數，則改為正數，但把x取倒數
        if(n<0) {
            n = -n;
            x = 1/x;
        }
        return pow(x,n);

    }

    private double pow(double x, int n) {
        if(n==0) return 1;
        if(n==1) return x;
        double half = pow(x,n/2);
        //偶數個
        if(n%2==0) {
            return half*half;
        }
        //奇數個
        return half*half*x;
    }
}
這種方法的時間複雜度就是O(logN)了。

以上，就是對數據結構中「 遞歸 」的一些思考。

碼字不易啊，喜歡的話不妨轉發朋友，或點擊文章右下角的“在看”吧。?

本文原創發佈於微信公眾號「 不止思考 」，歡迎關注。涉及 思維認知、個人成長、架構、大數據、Web技術 等。