上台阶（递归）

美女老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数， 求不同的走法数。
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。
输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1
<= N <= 30输出不同的走法数，每一行输入对应一行。
输出
不同的走法数，每一行输入对应一行输出
样例输入
5
8
10
样例输出
8
34
89

用递归将问题分解为规模更小的子问题进行求解

n级台阶的走法 = 先走一级后，n-1级台阶的走法 + 先走两级后，n-2级台阶的走法

f(n) = f(n-1)+f(n-2)

边界条件：当n=1时，f(n)=1;当n=2时，f(n)=2

#include<iostream>
using namespace std;
int n;//台阶数

int stairs(int n);
int main()
{
	while (cin >> n)
		cout << stairs(n) << endl;
	return 0;
}

int stairs(int n)
{
	if (n == 1)//边界条件1：如果还有一级台阶，只有一种走法
		return 1;
	if (n == 2)//边界条件2：如果还有二级台阶，只有两种走法
		return 2;
	return stairs(n - 1) + stairs(n - 2);
}