斐波那契序列的基本实现

 

今天实在没事干，刚好别人问了我下斐波那契面试怎么回答。就写了三个最基本的方式来弄吧。

import java.util.Stack;

public class StackAndRechurisive {

    public static void main(String[] args){
        int n = 8;
        System.out.println(StackMethod(n));
        System.out.println(ForMethod(n));
        System.out.println(Fac(n));
    }
    
    public static double Fac(int n){
        if(n==0)
            return 1;
        else if(n==1)
            return 1;
        
        else
            return Fac(n-1)+Fac(n-2);
    }
    
    public static double StackMethod(int n){
        if(n==0)
            return 1;
        if(n==1)
            return 1;
        Stack<Integer> stack = new Stack<Integer>();
        int result=0,temp=0;
        if(n>=2){
            stack.push(n-1);
            stack.push(n-2);
            n--;
        }
        while(stack.size()>0){
            temp = stack.pop();
            if(temp==0)
                result+=1;
            else if(temp==1)
                result+=1;
            else{
                stack.push(temp-1);
                stack.push(temp-2);
            }
        }
        return result;
        
        
    }
    
    public static double ForMethod(int n){
        double[] array = new double[n+1];
        array[0]=1;
        array[1]=1;
        for(int i=2;i<=n;i++)
            array[i]= array[i-1]+array[i-2];
        return array[n];
    }
}

 

说明：最基本的递归，就是反应下你对递归的了解程度【终止条件，迭代】。
           栈方式：反应你对递归的理解，函数递归通常都是拿栈来实现的，那当然一般的递归函数你都可以去用栈完成了。
           循环方式：因为上面两种都是非常浪费内存空间，并且做了大量的重复用算。因此，采用另开临时空间标记的方式进行了，这样可以记住前面求过的值。