笔试题（6）

题目：Fibonacci数列的递归和非递归解法。

 

解答： 如下所示：

 

/**
 * @author [e-mail]
 * 
 *         Time: 2011-8-25 下午01:52:10
 */
public class Test4 {

	public static void main(String[] args) {
		Test4 test = new Test4();
		for(int i=1; i<50; i++){
			System.out.print(test.getFactorial(i) + " ");
		}
		System.out.println("");
		for(int i=1; i<50; i++){
			System.out.print(test.getgetFactorialRec(i) + " ");
		}
	}

	public long getFactorial(int num) {
		long ff = 1, fs = 1;
		if(num == 1 || num == 2)
			return 1;
		for(int i=3; i<=num; i++){
			fs = ff + fs;
			ff = fs - ff;
		}
		return fs;
	}

	public long getgetFactorialRec(int num) {
		if (num == 1 || num == 2) {
			return 1;
		}
		return getgetFactorialRec(num - 1) + getgetFactorialRec(num - 2);
	}

}