题目：第39级台阶

小明刚刚看完电影《第39级台阶》。

离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!

站在台阶前，他突然又想着一个问题：

如果我每一步只能迈上1个或2个台阶。

先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。

那么，上完39级台阶，有多少种不同的上法呢？

请你利用计算机的优势，帮助小明寻找答案。

---

分析：首先代入到具体情境中，第一步你买了左脚，但是迈了一级还是两级台阶呢？

           迈完之后，第二步右脚在先前的基础上又要迈一级还是两级？

           想到这里，脑海中应该有一副二叉树的图像。（此题不使用二叉树，仅帮助理解）

           选择方法——递归，进行函数的嵌套

           要注意的是递归结束的条件设定：①台阶数为39

                                                                 ②步数为偶数

           对于递归不太理解的可以参考其他博客。

---

代码如下：提供了两种角度，便于理解

角度一：从第39级台阶开始往下迈

个人对于代码中递归使用的理解，如有错误还请指正：

首先剩余39层台阶，步数为0；

然后进入函数，依次执行迈一层和迈两层的函数，注意是依次执行；

之后，在刚才的两次依次执行的函数下，又分别依次执行迈一层和迈两层的函数，想象一下，就是二叉树的样子；

最后，想象一下有越来越多分支的树向下延伸的样子，当某一分支到头了（也就是剩余层数为0，步数为偶数），递归就结束了。

像这样的分支有很多很多，且树的高度不一定一样。

由于满足条件的分支很多，所以每找到一个，都需要保留到计数器中。

#include<iostream>
using namespace std;

int c=0;//用作计数器

void f(int n,int step)
{   //n用于表示剩余的楼梯的层数，当等于0或小于0时停止递归
	//step是走过的步数，用来判断是否是偶数，是否符合要求
	if (n < 0)return;            //退出的条件1
	if (n == 0 && step % 2 == 0) //退出的条件2
	{
		c++;
		return;
	}
	f(n - 1,step + 1);          //这一步走了一个台阶
	f(n - 2, step + 1);         //这一步走了两个台阶
}
int main()
{
	f(39,0);                    //初始状态：剩余39层台阶，第0步
	cout << c<<endl;
}

角度二：从第0级台阶开始往上迈

​
#include<iostream>
using namespace std;

int c=0;//用作计数器

void f(int n,int step)
{
	if (n > 39)return;
	if (n == 39 && step % 2 == 0)
	{
		c++;
		return;
	}
	f(n + 1,step + 1);
	f(n + 2, step + 1);
}
int main()
{
	f(0,0);
	cout << c<<endl;
}

​

结果：51167078