题目
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39
分析
斐波拉切数列简单的说就是0，1，1，2，3，5，8……，简单的说就是后一项是前两项的和，很容易想到使用递归。既简单又方便， 几行代码就搞定了。于是有了如下的代码：
public class Solution {
public int Fibonacci(int n) {
if(n>39)
return -1;
if(n == 0){
return 0;
}else if(n == 1 || n == 2){
return 1;
}else{
return Fibonacci(n-2) + Fibonacci(n- 1);
}
}
}
但是输出的结果就有问题了：
这里我试了一下条件改为（n>=39）,复杂度是降低了，但是n=39这个测试用例肯定通不过，那么就发现 这个题精华的部分就在这个条件n=39， 一定是程序还有优化的地方。
考虑一个简单的过程，n = 5的时候，具体的递归调用如下：
（1）Fibonacci(4) + Fibonacci(3)；
（2）Fibonacci(3) + Fibonacci(2)；
（3）Fibonacci(2) + Fibonacci(1)；
（4）Fibonacci(1) + Fibonacci(0)；
这个计算过程就像下图一样：
这里我们发现Fibonacci(3)，Fibonacci(2)，Fibonacci(1)都被重复的调用，重复调用意味着重复计算，会消耗栈空间和时间。
如果还要继续使用递归，而不使用循环，就要重新优化了。这个时候考虑尾递归。所谓的尾递归就是：
在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归，是递归的一种特殊情形。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。
尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧——而是更新它，如同迭代一般。尾递归因而具有两个特征： 调用自身函数(Self-called)； 计算仅占用常量栈空间(Stack Space)。 而形式上只要是最后一个return语句返回的是一个完整函数，它就是尾递归。
由于尾递归没有开辟更多的栈空间，同时，只会存储当前的函数，而释放之前调用的函数，所以可以节省更多的空间。
代码
public class Solution {
public int Fibonacci(int n) {
if(n>39)
return -1;
if(n == 0){
return 0;
}else if(n == 1 || n == 2){
return 1;
}else{
return Fib(n,0,1);
}
}
private int Fib(int n,int a,int b){
if(n == 0){
return a;
}else{
return Fib(n - 1,b,a + b);
}
}
}
但是对于斐波拉切，我认为还是使用循环是最好的：
（1）n=0,返回0
（2）n=1，返回1
（3）使用两个变量分别记录前一个和前两个数的大小，每次求出了第n个就对这两个数进行跟新
public class Solution {
public int Fibonacci(int n) {
if(n<0 || n>39)
return 0;
// 记录结果
int result = 0;
// 记录前前一个数
int prePreNumber = 0;
// 记录前一个数
int preNumber = 1;
if (n ==0 ){
return 0;
}
if(n == 1){
return 1;
}
for(int i = 2;i <= n;i++){
result = prePreNumber + preNumber;
prePreNumber = preNumber;
preNumber = result;
}
return result;
}
}
