递归(斐波那契数列)

斐波那契数列

1、1、2、3、5、8、13、21、34

public static int add(int n){
	if(n==2||n==1){
		return 1;
	}
	return add(n-2)+add(n-1);
}

//第二种方式
public static int add2(int n){
	if (n == 2 || n == 1)
		return 1;
	int prev = 1, curr = 1;

	for (int i=3;i<=n;i++) {
		int sum = prev + curr;
		prev = curr;
		curr = sum;
	}
	return curr;
}