先看下百度百科对斐波拉契数列的定义：
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*） 反正就是一句话：斐波拉契牛逼。
第一种数组实现方法：基于数组实现
/**
* @author 薛定谔的猫
* 斐波拉契数列数组实现
* 求前二十项*/
public class Main {
public static void main(String[] args) {
getFib(20);
}
public static int getFib(int n){//核心函数
if (n<0) {
return -1;//小于0是没有意义的
}else if (n == 0) {
return 0;//等于0其实也没什么意义
}else if (n == 1||n == 2) {
return 1;//第一项和第二项都是1
}else {
int[] fibAry = new int[n + 1];
fibAry[0] = 0;
fibAry[1] = fibAry[2] = 1;
for(int i = 3;i<=n;i++) {
fibAry[i] = fibAry[i-1] + fibAry[i-2];//当前项等于后一项加上后两项
System.out.println("第" + i + "项"+fibAry[i]);//输出当前项
}
return fibAry[n];//返回当前项
}
}
}
第二种实现方法：基于变量实现
/**
* @author 薛定谔的猫
* 斐波拉契数列变量实现
* 求前二十项*/
public class Main {
public static void main(String[] args) {
getFib(20);
}
public static int getFib(int n){//核心函数
if (n<0) {
return -1;//小于0是没有意义的
}else if (n == 0) {
return 0;//等于0其实也没什么意义
}else if (n == 1||n == 2) {
return 1;//第一项和第二项都是1
}else {
int temp = 0;//当前项变量
int a = 1;//第一项
int b = 1;//第二项
for(int i = 3;i<=n;i++) {
//变量互换值
temp = a+b;//当前项等于前两项相加
a = b;//前两项互换值
b = temp;//当前项赋值给前一项
System.out.println("第" + i + "项"+temp);//输出当前项
}
return temp;//返回当前项
}
}
}
第三种实现方法：递归实现（用递归的都是神）
递归定义：简单的说就是自己调用自己。
/**
* @author 薛定谔的猫
* 斐波拉契数列变量实现
* 求前二十项
* 这种方法最简单，但是最占用内存，特别是当n很大的时候
*
*
* 为什么递归得效率低？
* 递归效率低是函数调用的开销导致的。在一个函数调用之前需要做许多工作，
* 比如准备函数内局部变量使用的空间、搞定函数的参数等等，这些事情每次调用函数都需要做
* ，因此会产生额外开销导致递归效率偏低，所以逻辑上开销一致时递归的额外开销会多一些当然了，
* 通过有意识的组织代码的写法可以把某些递归写成尾递归，尾递归可以进行特殊的优化所以效率
* 会比普通的递归高一些，也不会因为递归太多导致栈溢出遍历树还不用递归的话，那么人肉写一个栈
* +深度优先遍历或者人肉队列+广度优先遍历，再辅以黑魔法给栈或者队列提速，应该会比递归快一些，
* 加速幅度和语言和写法相关，但在大多数情况下我觉得是得不偿失的，花了很大精力很可能效率提升不
* 明显
*
* 此回答转自知乎
* */
public class Main {
public static void main(String[] args) {
for(int i = 1;i<=20;i++) {
System.out.println("第" +i + "项" + getFib(i));
}
}
public static int getFib(int n){//核心函数
if (n<0) {
return -1;//小于0是没有意义的
}else if (n == 0) {
return 0;//等于0其实也没什么意义
}else if (n == 1||n == 2) {
return 1;//第一项和第二项都是1
}else {
return getFib(n-1) + getFib(n-2);//返回当前项,核心递归
}
}
}
最后说一句，斐波拉契牛逼。