算法|C | 汉诺塔和青蛙跳台阶问题算法|函数递归

前言
汉诺塔问题
青蛙跳台阶问题
结语

前言相信很多小伙伴和我一样，对于函数递归的方法一直掌握的不太好，总是不知道该怎么使用函数递归这个方法，也不知道该什么时候用这个方法。
今天我就和大家一起来看一看两道函数递归的经典题目。
汉诺塔问题和青蛙跳台阶问题。
汉诺塔问题

文章图片

题目的大概意思是：
一共有3根柱子，其中A柱子上有空心圆盘，圆盘串在A柱子中，而且圆盘的半径是由下到上依次增大。每次只能移动一个圆盘，最后使得全部圆盘串在C柱子中且圆盘半径也是由下到上依次增大。
大家可以先思考一下这个问题哦。
分析如下：
【算法|C | 汉诺塔和青蛙跳台阶问题】我们先从简单的情况入手，假如只有一个圆盘，那么这个问题就十分简单，只需要把圆盘直接从A移动到C即可。

文章图片

假如有两个圆盘，这个时候方法也很容易想到，我们可以把上面的圆盘编号为1，下面的圆盘编号为2，我们只需要先把1号圆盘放到B上，再把2号圆盘放到C上，最后把1号圆盘放到C上即可。

文章图片

当A上一开始就有3个圆盘时，我们同样可以从从上到下以此编号为1、2、3，我们可以这样做：先把1和2整体想办法放到B上，在把3放到C上，然后再把1和2整体放到C上。
具体步骤如下：1放到C中，2放到B中，1放到B中，3放到C中，1放到A中，2放到C中，1放到C中。

文章图片

文章图片

同样的，当圆盘有4个的时候，我们也可先把1、2、3看成一个整体，先把这个整体放到B中，然后把4放到C中，在把1、2、3这个整体放到C中。那么把1、2、3这个整体放到B中这个过程，又可以拆开成为1和2为整体与3的问题。这样，我们就实现了复杂问题转化为简单的问题。
这里面有一个很重要的思想：大事化小。
而这就是递归的重要思想。
具体代码如下：

//汉诺塔问题 //用递归来解决 #includevoid hannuota(int n ,char A ,char B,char C) { //如果只有一层，那么只需要直接从A移动到C即可 if (1 == n) {printf("%c -> %c\n", A, C); } else {//如果不止有一层，那么我们就先把最上面的n-1层放到B上，再把最下面的一层从A放到C中 //再把剩下的n-1这个整体从B移动到C hannuota(n-1,A, C, B); printf("%c -> %c\n", A, C); hannuota(n - 1, B, A, C); }}int main() { int n = 0; //输入汉诺塔的方块的层数 scanf("%d", &n); hannuota(n,'A','B','C'); //调用函数并把层数n传给函数，A,B,C表示三根柱子。 return 0; }

以上就是解决这个问题的代码了，其中打印的内容表示，从右往左移动，例如A -> C表示从A柱子中，拿最上面的一层，放到C中。
小伙伴们可以自己动手测试一下代码哦。
青蛙跳台阶问题问题大致为：一个青蛙，一次可以跳一个台阶，也可以跳两个台阶，如果现在有n个台阶，那么这个青蛙一共有多少中跳法？

文章图片

分析：
假设层数为N，f（N）表示一共有多少中跳法。
如果只有一个台阶，那么小青蛙只有一种跳法，那就是一次跳一层。
此时n = 1，f（N） = 1.
如果有两个台阶，那么小青蛙有两种跳法，要么是一次跳两层，一次就跳完；要么是一共跳两次，每次跳一层。
此时n = 2，f（N） = 2.
如果有三个台阶，那么我们从第三层台阶往回看，可以跳到第三层台阶的方法可以是从第二层跳到第三层，也可以从第一层跳到第三层。那么这时候，跳到第三层的跳法为可以跳到第一层的跳法加上可以跳到第二层的跳法。
同样的，如果有四个台阶，那么我们从第四层台阶往回看，可以跳到第四层台阶的方法可以是从第二层跳到第四层，也可以从第三层跳到第四层。那么这时候，跳到第四层的跳法为可以跳到第二层的跳法加上可以跳到第三层的跳法。
此时，f（N） = f（N - 1）+ f（N -2）.
代码的实现如下：

//青蛙跳台阶#includeint func(int n) { if (1 == n) return 1; else if (2 == n) return 2; else return func(n - 1) + func(n - 2); }int main() { int n = 0; //输入一共有多少层台阶 scanf("%d", &n); int ret = func(n); printf("当有%d层台阶时，一共有%d种跳法\n", n, ret); return 0; }

上述的就是解决青蛙跳台阶问题的代码了，小伙伴们可以去试验一下哦~
通过上面两个问题的分析，希望可以加深小伙伴们对于函数递归的理解~
结语这一次的分享，到这里就结束啦！
创作不易呀，如果大家觉得还不错的话，希望可以点个赞、收个藏、关个注哦~~
你们的支持是我创作最大的动力！！
由于本人能力有限，若有错误，希望指正！！
如果有更好的方法或者想法，也欢迎再评论区留言哦~