f(n) = f(n-1) + f(n-2) 实现（递归与非递归运行时间比较）

Fibonacci 算法递归实现与非递归实现时间比较：

public class Question1 {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long start,end;
		int n=50;
		start = System.currentTimeMillis();
		getWays(n);
		end = System.currentTimeMillis();
		System.out.println("Non recursive cost time :"+ (end-start));
		
		start = System.currentTimeMillis();
		getWays_1(n);
		end = System.currentTimeMillis();
		System.out.println("recursive cost time :"+ (end-start));
	
	}
	
	public static long getWays(int n){
		// TODO Auto-generated method stub
		long[] f = new long[n+1];
		f[1]=1;
		f[2]=2;
		for(int i=3;i<=n;i++){
			f[i]=f[i-1]+f[i-2];
		}		
		return f[n];
	}
	
	public static long getWays_1(int n){
		if(n==1){
			return 1;
		}
		if(n==2){
			return 2;
		}
		return getWays_1(n-1)+ getWays_1(n-2);
	}
}

运行结果：
Non recursive cost time :0
recursive cost time :99093