求解一道编程题

Question

用JAVA编写一方法，要求用递归实现打印输出斐波那契数列的第n个数，斐波那数列公式是U1 = 0,U2 = 1,Un = Un-1 + Un-2(当n>2时)。

Answer 1

public class Fibonacci {       
    public static void main(String[] args) {            
        getFibonacci(5);   
    }   
  
    private static int[] getFibonacci(int d){   
        int[] fib = new int[d];            
        fib[0] = 0;            
        fib[1] = 1;            
        for(int i = 2; i < fib.length; i++)                
            fib[i] = fib[i-1] + fib[i-2];            
        for(int i = 0; i < fib.length; i++)                
            System.out.print(fib[i] + " ");            
        System.out.println();      
        return fib;   
    }   
}  

Answer 2

这个递归的效率真是……
算F(30) 总共递归了1664079次，算到45就算不出了
public int F(int i){
if(i==1)
return 0;
if(i==2)
return 1;
return F(i-1)+F(i-2);
}

Answer 3

public int F(int i){
    if(i==1)
        return 0;
    if(i==2)
        return 1;
    return F(i-1)+F(i-2);
}