java编程裴波那契数列实现

  辞职不久，去一家公司面试，刚好遇到这个编程题。这题好像在哪见过，悲催的我没有做出来。也不算没有做出来，想错了。是前两个数相加，我做到相乘去了。一点也不细心，
  好好反省，回家把它重新做了一下，包括递归和非递归算法。

public class TestFei {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		for(int i=1;i<=20;i++){
			int k=printNum2(i);
			System.out.println(k);
		}
		
		for(int i=1;i<=20;i++){
	
			System.out.println(printNum(i));
		}
	}
	
	public static int printNum(int k){
		if(k==1||k==2){
			return 1;
		}else{
			int [] a = new int[k+1];
			a[0]=1;
			a[1]=1;
			for(int i=2;i<=k;i++){
				a[i]=a[i-1]+a[i-2];
			}
			return a[k-1];
		}
	}
	
	public static int printNum2(int k){
		if(k==1||k==2){
			return 1;
		}else{
			return (printNum2(k-1)+printNum2(k-2));
		}
	}

}