今天学习到了递归算法,下面是我对递归算法的知识总结,包含一些例题及分析,语言使用C++和Python,但掌握算法精髓后用其他语言也可以实现
递归算法
一种函数直接或者间接地调用自身的算法
递归算法包括两种情况
有递归边界
每一步执行动作一样
每调用一次规模缩小
结果通过一步步结果层层退出
经典的递归案例
C++代码
Python代码
递归的调用过程
递推阶段
回潮阶段
案例:学生年龄问题
第5个学生比第4个学生大2岁,第4个学生比第3个学生大2岁,第3个学生比第2个学生大2岁,第2个学生比第1个学生大2岁,第1个学生10岁,求第5个学生年龄
让我们分析一下这道题
这里的x=10就是递归边界,如图C++代码
Python代码
实战:汉诺塔问题
汉诺塔不用介绍了吧,不了解的请自行百度输入整数n,为圆盘个数,求圆盘的最简移动步骤
分析:
实现这个算法可以简单分为三个步骤:
把n-1个盘子由A移到B
把第n个盘子由A移到C
把n-1个盘子由B移到C 如图
代码
C++代码
Python代码
That's all~~~
Smart的小程序:
小编Smart
领取专属 10元无门槛券
私享最新 技术干货