[数据结构与算法]隔壁大妈看了直呼“so easy！”之C语言递归解决青蛙跳台阶问题

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶（不可后退）。求该青蛙跳上一个n级的台阶总共有多少种跳法？

思路

青蛙一次只可以跳1级台阶或者2级台阶，那么跳n级台阶的最后一步，必定是选择跳1级台阶或者跳2级台阶。

若青蛙选择最后一步跳1级台阶，则其前n-1级台阶的跳法种数等于跳n-1级台阶时的跳法总种数；

若青蛙选择最后一步跳2级台阶，则其前n-2级台阶的跳法种数等于跳n-2级台阶时的跳法总种数。

令f(n)表示跳n级台阶的总种数，则f(n)=f(n-1)+f(n-2)，n>2。

这样我们只要分别确定了跳1级台阶和2级台阶的总种数，就可以通过递归求出跳n级台阶的总种数。

f(1)=1;

f(2)=2;

...

f(n)=f(n-1)+f(n-2)

代码演示

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

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

int main()
{
	int n = 0;
	scanf("%d", &n);
    int ret = f(n);
	printf("%d\n", ret);

	return 0;
}