《c语言》青蛙跳台阶递归问题

题目：

        一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:跳上第一级台阶只有一种跳法:直接跳 1 级即可。跳上两级台阶,有两种跳法: 每次跳 1 级,跳两次; 或者一次跳 2 级.问要跳上第 n 级台阶有多少种跳法?

思路分析：

        首先我们可以考虑到，青蛙在只有一层台阶的时候只会有一种跳法，在两层台阶的时候会有两种跳法

                                                                      

那么我们尝试考虑一下如果有三个台阶呢，小青蛙可以有了多种选择，他可以选择一个一个         

  

也可以选择第一次跳一个台阶，第二次直接跳两个台阶

 

还可以选择第一次跳两个台阶，然后再跳一个台阶

 

那么综上所述，我们可以得到

如果有一个台阶的话，小青蛙有一种跳法；

如果有两个台阶的话，小青蛙有两种跳法；

如果有三个台阶的话，小青蛙有三种跳法；

如果有四个台阶的话，小青蛙有五种跳法；

……………………

那么我们可以考虑到，无非小青蛙的跳法就是n-1个台阶的跳法次数+n-2个台阶的跳法次数

所以我们代码可以如下所示

int frog(int n) {
	if (n == 1)return 1;
	else if (n == 2)return 2;
	else return frog(n - 1) + frog(n - 2);
}

 好了本次思路就分享到这~~感谢大家三连支持