递归----------上台阶问题

问题描述：

有一个楼梯，甲现在位于第0阶，每次可以上1阶，2阶，3阶，那么到达第N阶共有多少种走法？

思路：用递归的思想很容易解决，即 

• 先上1个台阶后的上法+先上两个台阶的上法+先上三个台阶的上法
• 边界条件： 当台阶 n==0，即认为是有一种方法，即不上台阶，当n<0时，没有台阶也就认为方法为0

递归函数如下

int statis(int n){
	if (n<0)
		return 0;
	if(n == 0)
		return 1;
	return statis(n-1)+statis(n-2)+statis(n-3);
} 

但是由于是尾递归，效率极低，而且所有的尾递归都可以改写长迭代的方式，于是

迭代函数如下

int statis(int n)
{
	int a1 = 1,a2 = 2,a3 = 4;
	int sum;
	if(n == 1)return a1;
	else if(n == 2) return a2;
	else if(n == 3 ) return a3;
	else{
		for(int i = 4; i<=n;i++){
		 sum = a1+a2+a3;
			a1 = a2;a2 = a3; a3 = sum;
		}
	}
	return sum;
}