【问题描述】C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
假设你正在爬楼梯，需要爬n级楼梯才能到达楼顶。每次你可以爬一或两级楼梯。你有多少种不同的方法可以爬到楼顶呢？C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入数据：C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
请输入楼梯的级数:5C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出结果：C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
爬5级楼梯一共有8种不同的爬法C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【题前思考】C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
根据问题描述，填写表5-2-2。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
表5-2-2 问题分析C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【解题思路】C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
很显然爬一级楼梯只有一种方案，爬两级楼梯有两种方案（一次爬一级和一次爬两级）。下面分析楼梯数量超过两级的情况。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3级楼梯C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
图5-2-1 爬3级楼梯的方案C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
从图5-2-1可知，爬3级楼梯的方法数=爬2级的方法数+爬1级的方法数=2+1=3种方法。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4级楼梯C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
图5-2-2 爬4级楼梯的方案C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
从图5-2-2可知，爬4级楼梯的方法数=爬3级的方法数+爬2级的方法数=3+2=5种方法。以此类推，我们可以得到爬n级楼梯的方法数。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
n级楼梯C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
图5-2-3 爬n级楼梯的方案C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
从图5-2-3可知，爬n级楼梯的方法数=爬n-1级的方法数+爬n-2级的方法数。前面的分析已经算到了n=4，那么当n=5、n=6、n=7，以至对于任意n我们都可以用这个方法推算出来。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
如果用stair(n)表示爬n级楼梯的方法数，则可以用数学公式代表刚才的推导过程：C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【程序代码】C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【代码分析】C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
①：定义函数stair(n)计算爬n级楼梯的方法数。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
②：当n=1，即只有一级楼梯时，方法数为1，当n=2，即只有两级楼梯时，方法数为2。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
③：对于n>2的情况，我们无法直接计算出结果，还要继续调用函数stair(n-1)和stair(n-2)，然后求它们的和才能算出爬n级楼梯的方法数。函数体中采用了递归调用。第②步中能得到明确函数值的部分称为尾递归。一个递归函数必须要有尾递归才能正确工作，否则就会陷入死循环。图5-2-4以n=5为例展示递归调用过程中数据传递的过程。C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
图5-2-4 爬5级楼梯函数递归调用过程C7U100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
