递归问题：上台~阶

只能一次上一层或两层台阶，输入台阶数，输出方法数

#include <iostream>

using namespace std;

int stairs(int n){
    //终止递归的条件
    if(n==0){
        return 1;
    }
    else if(n<0){
        return 0;
    }
    else{
        return stairs(n-1)+stairs(n-2);//第一次走一级台阶+第一次走两级台阶
    }
}

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

敲黑板
运用递归可以一步步的将复杂问题转化为简单一层的问题，比如这道题就将一次上台阶的过程分成两种情况，第一种是第一次跨一个台阶，第二种是第一次跨两个台阶。所以上一次台阶f(x)=f(x-1)+f(x-2)，这样不断递归下去。但是，仅仅这样是不能解决问题的，会变成无限递归，所以必须要为递归设立边界条件，即什么时候终止递归，开始计算，这样才能解决问题。