public class Feibo {

	static long[] temp = new long[1000000];

	static long fun1(int n){

		if(temp[n]!=0)

			return temp[n];

		if(n==1||n==2)

			return temp[1]=temp[2]=1;

		return temp[n]=fun1(n-2)+fun1(n-1);

	}

	static long fun2(int n){

		if(n==1||n==2)

			return 1;

		return fun2(n-2)+fun2(n-1);

	}

	//尾递归

	//fun2(1,0,5);

	static long fun2(long a,long b,int n){

		if(n==1)

			return a;

		return fun2(a+b,a,n-1);

	}

}