|
算法---递归
最近看到群里好多帖子的算法题都用到递归的，又有好多小伙伴们不太理解，这里我想写一点自己的看法给大家参考，希望大家多多指教，多多指点哈。
之所有很多小伙伴不理解是因为递归本身比较抽象，我也是在大学里先是听老师讲过一节课之后自己理解了好久，以为已经十拿九稳了，其实半桶水都算不上，直到之后参加蓝桥杯的比赛发现很多题用递归解比较简单，当然了效率不高。
一个经典的递归问题（汉诺塔问题）：有三根柱子，N个中间有个孔的圆盘，大小不一，有一个僧人，初始状态是所有圆盘从小到大依次在最左边的柱子上放着，僧人的任务就是将所有圆盘全部移动到最右边的柱子上，借助中间的柱子，移动规则是：每次只能移动一个圆盘，且小的圆盘只能放到大的圆盘上。问当柱子数确定时，需要多少步能移动完？
当柱子个数少时，大家都能通过思考解决这个问题，但是当柱子个数多时，我们绝大多数人脑子就不够用啦。这是一个典型的用递归解决非常简单的问题。
何为递归：函数调用自己，就是递归。
转为递归解决：假如有100个圆盘，对僧人A来说这也太难了，于是他就想啊，我大小也是个领导啊，不能我自己做完所有事，于是他决定自己只做一件事，指挥他的手下僧人B将99个圆盘移动到中间柱子，他把最底下的圆盘（也就是最大的那个）移动到最右边的柱子，再指挥僧人C将99个圆盘从中间柱子移动到最右边的柱子上，这样就移动完了100个圆盘。这就是递归思想，将问题的规模缩小，本来是100个圆盘，缩小成移动1个+指挥别人移动99个。这个时候僧人B和C也可以这样做，自己只移动最底下一个，指挥手下移动剩下的98个。。。。。。。一直如此，直到某个被指挥的僧人只需要移动一个为止，这个就叫做递归出口。而递归体就是（目标：将N个圆盘从最左边移动到最右边；1.手下将N-1个圆盘移动到中间，2.自己将第N个圆盘移动到最右边，3.手下将N-1个圆盘从中间移动到最右边），这样一个看起来很困难的问题就解决了，当然了，这么简单的解决主要是依靠计算机的处理速度。递归问题是效率非常低的，因为要不停得调用函数，我们知道调用函数需要保护现场，进栈出栈等，因此如果不是特别需求，一般不常使用递归。
伪代码：
int count=0;//用于记录移动的次数
移动柱子(int m,char a,char b,char c)//m为当前仍需要移动的柱子数，柱子从左到右依次是a,b,c，最终目的就是将m个圆盘从a，移动到c
{
if（m==1）printf("%c->%c",a,c);//这是递归的出口，也就是说递归到此开始回溯了，如果没有出口，或者程序无法进入出口，那么递归就成了死循环
else
{
move(m-1,a,c,b);//指挥手下将m-1个盘子从a借助c移动到b
printf("%c->%c",a,c);//自己将最后一个也是当前最大的那个从a移动到c
move(m-1,b,a,c);//指挥手下将m-1个盘子从b借助a移动到c
}
}
通俗讲：
我要种10棵树，但是我懒，所以我自己只种一棵，雇了个工人头子种9棵，工人头子也懒，他自己也只种一棵，雇了个工人小头子种8棵，以此类推，每个人都只种一棵，直到某个人被雇时，只有一棵树的任务给他，这时候这个工人就是这个递归的出口。
| 
收藏
淘帖
踩
