指的是这样一个数列：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*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用
作答过程：因为从来不刷题，所以对于做题，感觉有点陌生了 （这里批判一下，刷题和八股文，社会资源的极大浪费，有时间做点有建设性的工作不好么，在学校做题还没做够么）
第一版：
言归正传，因为没有时间仔细思索，第一反应就是用斐波那契数列的定义，也就是递推公式来实现， Java代码如下：
public static int fib_v1(int n) {
if (n >= 3)
return fib_v1(n - 1) + fib_v1(n - 2);
return 1;
}
这个函数从逻辑上没有问题。但是计算的时间复杂性太高，实测发现，当参数n比较小的时候，比如n=10，函数能够很快返回结果，但是当n=101，我运行了一下好半天都没有结果，从理论上分析一下，每个fib函数，递归调用了两次fib函数（虽然两个参数略微减小了），基本节奏是一分为二，倍增，直觉应该是2的n次方的时间复杂度
第二版：
大学期间学数据结构课程的时候，有句话一直记到现在，以空间换时间，既然时间复杂度太高，而且还容易感觉到 fib(n-1）+ fib(n-2)几乎是把一个计算重复了两遍，这也就是前面分析的倍增复杂度的由来，比如当n=100的时候， 计算fib（99）+ fib（98），而fib（99）里面本身又会把fib（98）算一遍，那大可以把fib（98）的计算结果存下来，所以想到创建一个数组，用来存储fib函数的值
第二版Java代码如下：
public static int fib_v2(int n) {
int[] data = new int[1024];
data[1] = 1;
data[2] = 1;
for (int i = 3; i <= n; i++) {
data[i] = data[i - 2] + data[i - 1];
}
return data[n];
}
这时候再运行，fib_v2(101）很快就可以算出来了，但是得到的结果却是一个负数，显然是数值超过了int的最大表示范围，溢出了。于是改用BidDecimal类来替代int，代码就不贴了，运算结果为：573147844013817084101
但是面试官给的题目的参考答案中却是573147844013817200000，然后他问我哪个是对的，我一看明显我计算的结果精度更高，于是坚持我用BigDecimal计算的结果是对的。他们给的参考答案中的数字精度不够是浮点数表示方法带来的，至于为什么要用浮点数那就不知道他们咋想的了，可能是他们用的语言里没有BigDecimal这么好的工具吧，想到他们公司技术栈是Nodejs，于是我用javascript实现了一下，果然运算结果是573147844013817200000和参考答案一致。Javascript代码如下：
function fib_v2_js(n) {
var data = new Array(128)
data[1] = 1
data[2] = 1
for (var i = 3; i <= n; i++) {
data[i] = data[i - 2] + data[i - 1];
}
return data[n];
}
关于int溢出，浮点数精度问题先不多展开了，说回算法复杂度，从实现代码里的循环来看，这时候的复杂度是线性复杂度。空间复杂度也是线性的。 仔细观察一下，可以发现data数组，返回的只有最后一项，考虑到计算过程，也只用到了最后三项，所以可以考虑变量复用。存储必要的中间结果可以降低时间复杂度，但是与此同时也增加了空间复杂度。事实上，不难发现这个fib_v2函数不只是得到了第n项的结果，而是得到了斐波那契数列的第1到第n项，而需求只是第n项就可以了。
三个变量的实现如下：为了代码简单，数据类型仍然用int，只要记住当数值足够大的时候，用BigDecimal替换就可以了。
public static int fib_v3(int n) {
int a = 1;
int b = 1;
int c = 1;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
这样一来，空间复杂度从O（n）变成了O（C）
再仔细观察递推公式，当fib（n-1）计算出来之后，fib（n-3）已经不需要了，所以实际上只需要两个变量，就可以实现这个递推计算。因为3个变量压缩到2个变量意义不大，这里就不实现了。
补充：面试之后，我又回想了一下，斐波那契数列作为一个经典的递推数列，貌似有通项公式
然后搜索了一下，果然有通项公式，可惜是一个浮点数的指数运算，用它计算比递推加法还要耗时
