青蛙跳台阶问题是一个很经典的智力游戏，而在C语言里更是一道永恒不变的经典例题，今天我们就来对这个问题进行一下详解。
我们先来看题干：
一只青蛙，一次只能走一个台阶或者两个台阶，那么请问青蛙走n个台阶的时候可以有多少种方式？
对于此类求n项的问题，我们有一招叫做归纳法，归纳法，顾名思义，就是从小推大，我们不妨从1思考，n取1,2,3......时走的方式。
n=1，一种方法；n=2，两种方法；n=3，三种方法；n=4，五种方法......也可以接着取，不难发现是f（n）=f（n-1）+f（n-2），这就是我们常说的斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
所以，青蛙跳台问题就是变相的斐波那契数列问题。
下面我们就用C语言写一个斐波那契数列。
#include <stdio.h>
int Fun(int n)
{
if (n == 1)//n=1时，只有1种方式
return 1;
else if (n == 2)//n=2时，有两种方式
return 2;
else
return Fun(n - 1) + Fun(n - 2);//n>2时，开始符合斐波那契数列，用递归函数
}
int main()
{
int n = 0;
int ret = 0;
printf("青蛙要走几个台阶：");
scanf("%d", &n);
ret = Fun(n);
printf("青蛙有%d种走台阶方式\n", ret);
return 0;
}我们来运行一下看看效果
问题到这里其实已经结束了，但是当我们输入一个50看看：
我们发现结果迟迟出不来，原因是什么呢？是系统没有工作吗？还是程序出错了？其实是效率太低导致的结果，我们看下图
我们计算了n=3被计算的次数，发现n=3这一项的数字背计算了39088169次，这是一个相当大的数字，更何况我们一共要算50项，所以n=50时用递归效率极低。
这里我们给出了另一个思路：
#include <stdio.h>
int Fun(int n)
{
int a = 1;
int b = 2;
int c = 0;
if (n == 1)
return a;
else if (n == 2)
return b;
while(n>2)//用循环的方式来算斐波那契数列
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
int ret = 0;
printf("青蛙要走几个台阶：");
scanf("%d", &n);
ret = Fun(n);
printf("青蛙有%d种走台阶方式\n", ret);
return 0;
}我们发现，这种算法没有重复内容，计算效率也比较可观，但是不难发现，下面这个程序的复杂程度比上面的递归高很多。
于是最后总结一下，递归虽然很简洁方便，不过带来的可能是低效率，递归的核心是大事化小，未来当我们进入大厂工作时要权衡利弊，看看追求效率还是简洁，正确的选择方式可能带来更大的便利，本题如是。
以上就是青蛙跳台问题的详解以及递归方法的利弊关系，如果这篇文章对你有帮助，记得给一下小红心支持一下欧，下期再见，拜拜~
