[数据结构与算法]java实现斐波那契数列（递归和非递归）

基础知识：
斐波那契数列的运算规则为F(0) = 0;F(1) = 1;当n>=2时，F(n) = F(n-1) + F(n-2);
显然斐波那契数列具有递归的定义，下面用java递归实现当输入n时，返回F(n)的值：
算法思路：
首先判断当前n的值，当n=0时，返回0，当n=1时，返回1；否则返回f（n-1） + f（n-2）

class Fib {
    public int fib(int n) {
        return f(n);
    }
    public int f(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return f(n-1) + f(n-2);
    }
}

非递归实现斐波那契数列：
算法思路，递归是倒推，非递归是正推，循环进行累加即可：

class Fib {
    public int fib(int n) {
    	if(n==0){
    		return 0;
    	}
    	if(n==1){
    		return 1;
    	}
        int pre1 = 1;
        int pre2 = 0;
        int count = 2;
        int result = 0;
        while(count<=n){
        	result = pre1 + pre2;
        	pre2 = pre1;
        	pre1 = result;
        	count++;
        }
        return result;
    }
}