斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

在通常情況下我們很容易寫出一個計算斐波拉契數(shù)列的函數(shù)：

private static long diguiFeibo(int n) {
    if (n < 2) {
        return n;
    }
    return diguiFeibo(n - 1) + diguiFeibo(n - 2);
}

上面的代碼看起來很簡練，實際上它背后的計算流程還是很有很多步。比如說我們計算n = 50的時候的值，花費了大概56秒時間，計算的結(jié)果是12586269025。

long start = System.nanoTime();
long res = diguiFeibo(50);
long end = System.nanoTime();
System.out.println("total nano time == " + (end - start) + "  res == " + res);
//在i5 6500 cpu機器上執(zhí)行結(jié)果：total nano time == 56020760400  res == 12586269025

斐波拉契數(shù)列計算流程

可以很明顯的看出來這種計算方式所耗費的時間是相當漫長的，并且從上圖中我們可以看出來，一個F(N)可能存在多次被計算的過程，最后總的時間復(fù)雜度為O(2^n）。
那么我么有沒有辦法去優(yōu)化一下，讓其每一個F(N)只會計算一次呢，答案是肯定得。我們可以用一個容器來將每一步的計算結(jié)果儲存，簡單的我們可以用一個數(shù)組來存儲。所以我們的程序可以改寫成如下：

private static long diguiFeibo(long[] results, int n) {
    if (n < 2) {
        results[n] = 1;
        return n;
    }
    if (results[n] == 0) {
        results[n] = diguiFeibo(results, n - 1) + diguiFeibo(results, n - 2);
    }
    return results[n];
}

改進后的算法時間復(fù)雜度從O(2^n）時間復(fù)雜度降為O(n)，相當于從指數(shù)級別降到線性級別。執(zhí)行時間是6100納秒，大概0.006毫秒，可見這其中的時間差距有多大！

long start = System.nanoTime();
long res = diguiFeibo(new long[51], 50);
long end = System.nanoTime();
System.out.println("total nano time == " + (end - start) + "  res == " + res);
//在i5 6500 cpu機器上執(zhí)行結(jié)果：total nano time == 6100  res == 12586269025

從以上例子可以得出的結(jié)論：我們在進行遞歸的時候要考慮是否進行了一些重復(fù)計算，并且我們可以將前一步的計算結(jié)果通過參數(shù)的形式傳到當前這一步。
ps：加入我們不用遞歸，我們也是有辦法計算出斐波拉契數(shù)列的，我們來分析通項公式

F(n)=F(n-1)+F(n-2)
可見，在我們計算了F(n)的值之后，我們將F(n-1)的值變成F(n)，將F(n-2)的值變?yōu)镕(n - 1)，這樣不停的迭代，我們也是可以求出其值的。具體代碼如下：

private static long feibo(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    
    long s = 0;
    long s1 = 1;
    long s2 = 1;
    
    for (int i = 3; i <= n; i++) {
        s = s1 + s2;
        s2 = s1;
        s1 = s;
    }
    return s;
}

計算n=50的值，發(fā)現(xiàn)其耗時更優(yōu)，其時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，顯然這個方法也是比較優(yōu)秀的方法。

//在i5 6500 cpu機器上執(zhí)行結(jié)果：total nano time == 2900  res == 12586269025

關(guān)于遞歸傳值的經(jīng)典題目：
LeetCode 22 題

給出 n 代表生成括號的對數(shù)，請你寫出一個函數(shù)，使其能夠生成所有可能的并且有效的括號組合。
例如，給出 n = 3，生成結(jié)果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

這個題目是一道很經(jīng)典的利用遞歸傳參的題目，其解法如下：

class Solution {
    //總括號數(shù)
    int total = 0;
    public List<String> generateParenthesis(int n) {
        //left左括號"(", right右括號")"
        total = n;
        String curr = "";
        List<String> result = new ArrayList<>();
        parenthes(curr, result, 0, 0);
       return result;
    }
    //curr 當前括號形成的字符串，
    //result 存放所有可能結(jié)果的List
    //leftNum 已經(jīng)使用了的左括號數(shù)
    //rightNum 已經(jīng)使用了的右括號數(shù)
    private void parenthes(String curr, List<String> result, int leftNum, int rightNum) {
        if (leftNum == total && rightNum == total) {
            result.add(curr);
        }
        //使用左括號小于限定總數(shù)，可以繼續(xù)在后面加左括號
        if (leftNum < total) {
            parenthes(curr + "(", result, leftNum + 1, rightNum);
        }
        
        //使用左括號大于右括號，可以在后面加上右括號。
        if (leftNum > rightNum) {
            parenthes(curr + ")", result, leftNum, rightNum + 1);
        }  
    }
}