小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
去掉一个条件：偶数步，只问只能迈上1个或两个台阶的条件下一共有多少种走法呢
f(n=39) {return f(n-1)+f(n-2)}
考到了 斐波那契数列
n 表示剩下的阶梯数
step 表示已走的步数
在这里还需要注意全局变量和局部变量的区别
#include<iostream> using namespace std; int count; void f(int n,int step) { if(n<0) return; if(n==0&&step%2==0){ count++;return;} f(n-1,step+1); f(n-2,step+1); } int main() { f(39,0),cout<<count<<endl; return 0; }
原文：https://www.cnblogs.com/hrlsm/p/12507371.html