递归典型例题

编程入门行业动态更新时间:2024-10-07 10:14:30

递归典型例题

文章目录

前言
1.汉诺塔问题
1.1代码设计
- 1.1.1函数move设计
- 1.1.2递归函数设计
- 1.1.3汉诺塔总代码
2.青蛙跳台
- 2.1青蛙跳台总代码：
总结

✨✨✨学习的道路很枯燥，希望我们能并肩走下来！

编程真是一件很奇妙的东西。你只是浅尝辄止，那么只会觉得枯燥乏味，像对待任务似的应付它。但你如果深入探索，就会发现其中的奇妙，了解许多所不知道的原理。知识的力量让你沉醉，甘愿深陷其中并发现宝藏。

前言

本篇是对经典递归问题的讲解，有助于加深对递归的理解，如有错误，请在评论区指正，让我们共同进步！

本文开始

1.汉诺塔问题

汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：
每次只能移动柱子最顶端的一个圆盘；
每个柱子上，小圆盘永远要位于大圆盘之上；

大致思路：

第一根柱上n-1个圆盘通过第三根柱，移动到第二根柱
把第一根柱的第n个圆盘移动到第三根柱
借助第一根柱把第二根柱的n-1个圆盘移动到第三根柱上

动图演示：

查找规律分析：
圆盘数：移动次数
1 ------------- 1 =>2^1-1
2 ------------- 3 =>2^2-1
3 ------------- 7 =>2^3-1
4 ------------- 15 =>2^4-1
5 ------------- 31 =>2^5-1
… 根据移动次数与圆盘数规律可得结论：
n ------------ 2^n-1
用规律来验证自己是否代码正确

1.1代码设计

如何操作实现代码呢？
递归问题就是由大事化小，难的问题化为简单问题，我们总体思想就是把n个盘子移动逐渐化小，最终化到3个盘子，2个盘子，1个盘子的移动.

3个盘子移动示意图：

1.1.1函数move设计

我们来设计函数：
为详细说明每步我们怎么走，我们肯定需要一个移动函数，这里我们用move()函数，那它的参数如何来确定呢？
我们用了递归思想，把n个盘子移动最终转化为1个盘子移动，就是直接把盘子从sou(A柱子)放到tar(C柱子)
所以我们需要
s:起始位置(n-1个盘子已经移动)
t:目标位置
这样就有了函数头：void(int x,int y)

函数体我们还需要记录第几次移动，所以用全局变量count记录(也可以用static记录移动次数)
函数体只负责打印第几次，从哪移动到哪的：printf(“第%d次：%c -> %c\n”,count,s,t);
这样就有了 move函数代码：

void move( char s, char t)
{++count;//计算移动次数printf("第%d次:%c -> %c\n",count, s, t);
}

1.1.2递归函数设计

递归函数如何实现呢？
为了让代码更好理解，我们把三个柱子设为A柱(pole 1)：起始柱sou, B柱(pole 2)：辅助柱aux，C柱(pole 3)：目标柱tar;

在移动盘子时我们会考虑，有几个盘子需要移动，三根柱子，通过哪根柱子移动到哪根柱子
这是我们就需要参数：
n:盘子总数
sou(A柱):起始柱子
axu(B柱):辅助柱子
tar(C柱):最终要移动到的柱子
这就知道了函数hanio(int n, char sou, char aux, char tar)
调用时就需要：hanio(输入的数，‘A’， ‘B’，‘C’)
如何实现递归呢？
有n个柱子，每次我们就需要把n-1个盘子通过C柱子移动到B柱子上；再把第n个柱子放到C柱子上；再通过A柱子把n-1个盘子移动C柱子上就完成操作.*

递归移动其实也可以把问题看作几步把大象关进冰箱？
三步：①打开冰箱门(把n-1个盘子通过C柱移动到B柱)
②装进大象(把第n个盘子移动到C柱)
③关上冰箱门(通过A柱子把B柱子的n-1个盘子移动到C柱)

递归代码

void hanio(int n, char sou, char aux, char tar)
{if (n == 1)//只有一个盘子的时候{//从sou(A)移动到tar(C)move(sou, tar);}else{hanio(n - 1, sou, tar, aux);//把n-1个借助tar(C柱子)移动到aux(B柱子)move(sou, tar);//把sou(A柱)的第n个盘子移动到tar(C柱)上hanio(n - 1, aux, sou, tar);//把n-1个盘子借助sou(A起始柱子)移动到tar(C目标柱子)}
}

1.1.3汉诺塔总代码

#include<stdio.h>
int count = 0;
void move( char s, char t)
{++count;//计算移动次数printf("第%d次:%c -> %c\n",count, s, t);}
void hanio(int n, char sou, char aux, char tar)
{if (n == 1)//只有一个盘子的时候{//从sou(A)移动到tar(C)move(sou, tar);}else{hanio(n - 1, sou, tar, aux);//把n-1个借助tar(C柱子)移动到aux(B柱子)move(sou, tar);//把sou(A柱)的第n个盘子移动到tar(C柱)上hanio(n - 1, aux, sou, tar);//把n-1个盘子借助sou(A起始柱子)移动到tar(C目标柱子)}
}
int main()
{int n = 0;//输入盘子数量scanf("%d", &n);hanio(n, 'A', 'B', 'C');printf("\ncount=%d\n", count);return 0;
}

代码结果：

2.青蛙跳台

问题阐述：
一只青蛙可以跳上一级台阶，也可以跳上两级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？

图示：

通过图我们可以分析：

青蛙跳台问题
台阶数—跳法总数(跳法)
1 ------ 1 (1)
2 ------ 2 (11,2)
3 ------ 3 (111,12,21)
4 ------ 5 (1111,22,112,211,121,)
5 ------ 8
…
n ------ f(n-1)+f(n-2)

由规律可知，青蛙跳台阶方法满足斐波那契数列
如果有不清楚斐波那契数列的小伙伴可以点击下面的文章了解

点击这里，了解斐波那契数列，这里的习题有解释哦！

这是根据规律总结的图：实现递归时可以考虑下面的几种情况

2.1青蛙跳台总代码：

#include<stdio.h>
int Fib(int n)
{//台阶数少于1时if (n < 2){return 1;}else{//台阶数大于1时return Fib(n - 1) + Fib(n - 2);}
}
int main()
{int n = 0;//输入台阶总数scanf("%d", &n);//由规律我们可得青蛙跳台的方法成斐波那契数列int ret = Fib(n);prinf("%d\n", ret);return 0;