詹姆士的筆記本

費式數列(Fibonacci)

wiki：

數學上，費式數列式以遞迴的方式定義：

• F₀ = 0
• F₁ = 1
• Fn = F_n-1 + F_n-2

用文字來說費式數列由0和1開始，之後的數列由之前兩個數相加得出。

0,1,1,2,3,5,8,13,21,34,55,89,144,233.......

註：0不是第一項，而是第零項。

Loop

private static int fibloop(int n) {
	if(n==0)
		return 0;
	if(n==1)
		return 1;
	
	int f0=0;
	int f1=1;
	int fn=0;
	for(int i = 2; i<=n;i++) {
		fn = f0+f1;
		f0 = f1;
		f1 =fn;
	}
	
	return fn;
}

Recursive

private static int fibRecursive(int n) {
	return n == 0 ? 0 : n == 1 
		? 1 : fibRecursive(n - 1) + fibRecursive(n - 2);

}

TailRecursive

重點在於重頭開始加總，利用n來進行遞迴次數的控制項

private static int fibTailRecursive(int n) {
	return fibHelper(n , 0,1);
}
private static int fibHelper(int n ,int f0,int f1) {
	if(n==0)
		return f0;
	if(n==1)
		return f1;
	return fibHelper(n-1,f1,f0+f1);
}

物件方式

class Fibonacci{
	private List<Integer> fibSeries = new ArrayList<>();
	{
		fibSeries.add(0);
		fibSeries.add(1);
	}
	public int get(int n) {
		if(fibSeries.size()<n) {
			for(int i = fibSeries.size();i<=n;i++) {
				fibSeries.add(fibSeries.get(i-1)+fibSeries.get(i-2));
			}
		}
		return fibSeries.get(n);
	}
}

Reference：

• NotFalse 技術客 尾遞迴
• Openhome.cc 物件方式
• wiki