上楼梯经典题目（递归）

小明想要走上一个一共有n级阶梯的楼梯，每次只能上一级或者两级，问小明一共有多少种上楼梯的方式？（用递归方法实现）

输入：数字n，代表共有n级楼梯。

输出：数字a，代表有a种上楼梯方式。

解题思路：

自定义函数内操作分析如下：

1. 小明上到n级阶梯的上一步所在位置只有两种情况。

   1--小明在n-1级阶梯上。记此时上楼方式有ways（n-1)次

   2--小明在n-2级阶梯上。记此时上楼方式有ways（n-2)次

2. 所以ways（n）就等于ways（n-1)与ways（n-2)之和

3. 依2，ways（n-1）就等于ways（n-2)与ways（n-3)之和

   ways（n-2）就等于ways（n-3)与ways（n-4)之和

   ways（n-3）就等于ways（n-4)与ways（n-5)之和

   …………

4. 再而ways（1）=1和ways（2）=2，函数ways内的操作便浮现而出了

源代码

#include
using namespace std;

int ways(int n)
{
	if (n == 1 || n == 2)
		return n;
	return ways(n - 1) + ways(n - 2);
}

int main()
{
	int n;
	cin >> n;

	int a;
	a = ways(n);

	cout << a;
	return 0;
}