首页 > 代码库 > Fibonacci的递归实现和非递归实现

Fibonacci的递归实现和非递归实现

递归实现很好实现,主要就是递归和分治的思想。

非递归实现可以使用数组来实现,一般递归是将初始值放在最后来使用;非递归可以考虑以初始值(fib(0)=0;fib(1)=1;)为基础,利用循环来进行计算。

代码:

public class Fibonacci{
	public int getResultByRecursion(int n){
		if(n == 0){
			return 0;
		}else if(n == 1){
			return 1;
		}else{
			return getResult(n-1)+getResult(n-2);
		}
	}
	public int getResult(int n){
		int[] temp = new int[n];
		temp[0] = 0;
		temp[1] = 1;
		for(int i=2;i<temp.length;i++){
			temp[i] = temp[i-1] + temp[i-2];
		}
		return temp[n-1];
	}
	public static void main(String[] args){
		int n = 20;
		Fibonacci obj = new Fibonacci();
		System.out.println("the recursion result is "+obj.getResultByRecursion(n));
		System.out.println("the nonrecursion result is "+obj.getResult(n));
	}
}

共勉!

Fibonacci的递归实现和非递归实现