通过c语言和java的递归来实现青蛙跳台的问题

通过c语言和java的递归来实现青蛙跳台的问题

问题描述：一只青蛙一次能够跳1阶或者2阶台阶，一共有n阶台阶
 这只青蛙一共有几种跳法

当我们一开始看到此问题时肯定会一下子摸不到头脑，没有想法，既然这样我们尝试使用笨办法来寻找其中的规律

当台阶数为1时只有一种跳法，台阶数为2时则有两种

台阶数为3时，则需要分类了

青蛙第一次跳1阶，则剩下了2阶，那么与台阶数总共为2阶的跳法相同（两种）

当青蛙第一次跳2阶时，则剩下了1阶台阶，那么就与总台阶数为1阶时相同（一种）

由上述可知台阶数为3时跳法为3

设总台阶数为：n , 跳法：sum

通过上述，我们可以总结出一个规律，除了第一二级台阶其余的台阶数的跳法为：n-1时的台阶数跳法加上n-2时的台阶数跳法

                        台阶数：n            跳法：sum

                                      1                         1

                                      2                         2

                                      3                         3

                                      4                         5

                                      5                         8

当我们使用递归的思路来实现青蛙跳台阶问题时

其实与高中学习的分类用加类似

c语言的实现如下：

#include
int jump(int n)
{
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	return jump(n - 1) + jump(n - 2);
}
int main()
{
	int n = 0;
	scanf_s("%d", &n);
	int ret = jump(n);
	printf("%d", ret);
	return 0;
}

java的实现如下：

public class TestDemo
{
    public static int jump(int n)
    {
        if(n == 1)
        {
            return 1;
        }
        else if(n == 2)
        {
            return 2;
        }
        return jump(n-1)+jump(n-2);
    }
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int ret = jump(n);
        System.out.println(ret);
    }
}