斐波那契数列的递归与非递归的3种实现方式。
递归是一种常用的解决问题的思路，使用递归的方法编程，会使程序看起来简洁清晰，如果我们写一段java的递归代码，java的底层是用栈来实现递归的，不过递归不断的出栈和入栈操作，使递归算法的性能大受影响。正因为递归算法在时间和空间上都些限制，在实际应用中，我们一般采用递归算法来分析问题，使用非递归算法来解决问题，
本文将从实现斐波那契数列入手，来讨论递归与非递归的实现与转化，
斐波那契指的是这样一个数列：0、1、1、2、3、5、8、13、21.....它所遵从的规律是f(n)=f(n-1)+f(n-2).
1、递归的方式来实现Fibonacci Sequence。
使用递归的方法需要注意两个问题，一个是递归的出口，另外一个就是递归的逻辑关系，所谓的逻辑关系，就是f(n)=f(n-1)+f(n-2)。
public static int Fib(int n){
if(n<=0)
return 0;
if(n==1){
return 0;
}
if(n==2){
return 1;
}
return Fib(n-1)+Fib(n-2);
}
程序中的n==1和n==2就是递归的出口。由于java底层是用栈来实现的。不断的出栈和入栈，而且栈将所有的中间值都存了起来，所以时间和空间上还是打了很大的折扣的。
2.非递归的方式来实现FiboNacci Sequence。
public static int Fib(int n){
int pre_1=0,pre_2=0,temp;
for(int i=1;i<=n;i++){
if(i==1){
pre_2=0;
}
if(i==2){
pre_1=0;
pre_2=1;
}
temp=pre_2;
pre_2=pre_1+pre_2;
pre_1=temp;
}
return pre_2;
}
程序中采用了两个临时变量来存储中间值，pre_1和pre_2。这样就减少了空间的消耗。执行效率也比第一种效率高。
3.用栈来实现FiboNacci Sequence。既然逻辑关系是f(n)=f(n-1)+f(n-2)。要得到最终结果还是要靠这个逻辑关系，唯一不同的是要找一个地方来存中间值而已。递归是程序自己用栈来存的，第二种做法是用的两个变量来存的。我们来模拟程序实现递归的办法来消除递归。
public static int Fib(int n){
Stack<Integer> s=new Stack<Integer>();
int top=0;
if(n==0)
return 0;
while(top<=n){
if(top==0){
s.push(0);
top++;
continue;
}
if(top==1){
s.push(1);
top++;
continue;
}
s.push(s.get(top-1)+s.get(top-2));
top++;
continue;
}
return s.peek();
}
这段程序就是用栈存储了所有的中间值，执行 效率和空间上都不及第二种算法。