斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
在通常情况下我们很容易写出一个计算斐波拉契数列的函数：
private static long diguiFeibo(int n) {
if (n < 2) {
return n;
}
return diguiFeibo(n - 1) + diguiFeibo(n - 2);
}
上面的代码看起来很简练，实际上它背后的计算流程还是很有很多步。比如说我们计算n = 50的时候的值，花费了大概56秒时间，计算的结果是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机器上执行结果：total nano time == 56020760400 res == 12586269025
斐波拉契数列计算流程
可以很明显的看出来这种计算方式所耗费的时间是相当漫长的，并且从上图中我们可以看出来，一个F(N)可能存在多次被计算的过程，最后总的时间复杂度为O(2^n）。
那么我么有没有办法去优化一下，让其每一个F(N)只会计算一次呢，答案是肯定得。我们可以用一个容器来将每一步的计算结果储存，简单的我们可以用一个数组来存储。所以我们的程序可以改写成如下：
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];
}
改进后的算法时间复杂度从O(2^n）时间复杂度降为O(n)，相当于从指数级别降到线性级别。执行时间是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机器上执行结果：total nano time == 6100 res == 12586269025
从以上例子可以得出的结论：我们在进行递归的时候要考虑是否进行了一些重复计算，并且我们可以将前一步的计算结果通过参数的形式传到当前这一步。
ps：加入我们不用递归，我们也是有办法计算出斐波拉契数列的，我们来分析通项公式
F(n)=F(n-1)+F(n-2)
可见，在我们计算了F(n)的值之后，我们将F(n-1)的值变成F(n)，将F(n-2)的值变为F(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的值，发现其耗时更优，其时间复杂度为O(n)，空间复杂度为O(1)，显然这个方法也是比较优秀的方法。
//在i5 6500 cpu机器上执行结果：total nano time == 2900 res == 12586269025
关于递归传值的经典题目：
LeetCode 22 题
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
这个题目是一道很经典的利用递归传参的题目，其解法如下：
class Solution {
//总括号数
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 存放所有可能结果的List
//leftNum 已经使用了的左括号数
//rightNum 已经使用了的右括号数
private void parenthes(String curr, List<String> result, int leftNum, int rightNum) {
if (leftNum == total && rightNum == total) {
result.add(curr);
}
//使用左括号小于限定总数，可以继续在后面加左括号
if (leftNum < total) {
parenthes(curr + "(", result, leftNum + 1, rightNum);
}
//使用左括号大于右括号，可以在后面加上右括号。
if (leftNum > rightNum) {
parenthes(curr + ")", result, leftNum, rightNum + 1);
}
}
}
网友评论