递归算法与汉诺塔

目录递归核心思想关键示例阶乘斐波那契数列汉诺塔题目/规则思考找基线条件疑问为什么第一步1号一定要去C思考怎么“递”疑问怎么就实现了过一遍手动演绎递归过程n 3时递归核心递归函数自己调用自己两个必备条件缺一不可否则无限栈溢出基线条件终止条件满足条件直接返回不再递归调用防止死递归。递归条件把原问题拆解成规模更小、结构相同的子问题。大事化小直到最小可直接求解的情况再逐层返回合并结果。思想关键①不要试图一层一层跟踪全部调用我认为最关键的一条就是不要去质疑自己写的递归或许莫名其妙地就写对了误区手动去模拟每一层递归的执行栈深一大就混乱。正确思维相信递归函数是正确的数学归纳法思想。假设f(n-1)能正确完成任务我只要写好f(n)和f(n-1)的关系即可。汉诺塔相信 hanoi (n-1, ...) 可以把 n-1 个盘子完整挪好不用关心它内部怎么挪。② 递归分为两个阶段递、归递向下不断拆分问题函数不断调用自身压入栈直到碰到基线条件。此时还没有返回结果。归向上回溯到达基线开始返回子问题算出结果逐层向上合并得到大问题答案。阶乘递fact (4)→fact (3)→fact (2)→fact (1)归1→2→6→24③ 递归的本质利用函数调用栈保存中间状态每一次递归调用都会产生独立的局部变量保存在栈帧里。 回溯的时候自动恢复上一层函数的上下文。汉诺塔打印移动步骤就是回溯 / 递过程中输出状态。示例阶乘公式#include stdio.h using namespace std; int fact(int n) { if (n 1 || n 0) // 基线条件 return 1; return n * fact(n - 1); // 递归拆成更小子问题 } int main() { cout fact(4); return 0; }调用过程fact(4)fact(4)4*fact(3)→fact(3)3*fact(2)→fact(2)2*fact(1)→fact(1)1然后回溯2*12→3*26→4*624斐波那契数列公式#include stdio.h #include iostream using namespace std; int fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); } int main() { cout fib(4); return 0; }缺点大量重复计算效率低。汉诺塔今天尝试了在知道要用递归的前提下试着写了汉诺塔结果莫名其妙地写对了。很开心。之后又花了一小下午弄懂其中的原理。题目/规则起始有3 根柱子一般命名A源柱、B辅助柱、C目标柱有n 个大小互不相同的圆盘一开始全部叠在 A 柱大盘在下小盘在上依次堆叠。移动规则一次只能移动 1 个圆盘圆盘只能从一根柱子顶部拿放到另一根柱子顶部任何时刻不能把大盘放在小盘上面目标把全部 n 个圆盘从 A 柱完整移动到 C 柱移动过程遵守上面规则。思考普通的线性运算很难实现用递归最好写以三个n 3为例找基线条件首先想基线条件当n 1时将1号盘从当前柱移动到目标柱并且返回完成“归”。注意这里我没有说从A柱移动到C柱。因为在递归中你无法确定1号盘当前在哪个柱子也不能确定1号盘去哪个柱子。疑问为什么第一步1号一定要去C或许你会问只有一个盘的时候肯定要A - C那多个盘的时候1号盘不能现A - B结论是确实可以但不是最优解了。可以这么理解如果一个柱子的顶端是1号盘。那这个柱子就”死了“——此时这个柱子不能再移入任何的盘子若一开始就将1号盘移动到B柱2号会去C想要再操作只能进行1号盘B - C但这样已经gameover了——两个最小的在C柱上已经不可能实现最短路径了。思考怎么“递”现在不以三个为例了个数太少容易使人想走”捷径“假如现在有八个盘先写个函数模板void hanruo(int n, char ori, char buf, char dest)n为个数ori为柱当前所在的,buf为当前的缓存柱子dest是当前目标移动的柱。注意以上的参数只是针对当前状态这对理解特别重要——因为递归中谁做缓冲柱谁做目标柱都不一定当然第一层的ori buf dest就分别是A B C看最外层当n 8输入进函数后在写入基线条件后要思考面对这个八层的塔要干什么我们想要把1~7层全部挪到B柱来解放8号盘——将其移动到C这是将8号盘移动到C的唯一方式所以也其他没异议于是就开始递归void hanruo(int n, char ori, char buf, char dest) {//ori - A buf - B dest - dest if (n 1) { printf(%d号盘从%c移动到%c\n, n, ori, dest); return; } hanruo(n - 1, ori, dest, buf);hanruo(n - 1, ori, dest, buf);这一句,就表示将n - 1,也就是前七层从oriA以destC为缓冲移动到bufB也就实现了我们想要的效果疑问怎么就实现了这也没写啥具体的代码怎么就实现这个功能了确实我们代码还没写全逻辑还没闭环不了解也没事接着看就好了。之后就要将8号盘移动到Cvoid hanruo(int n, char ori, char buf, char dest) { if (n 1) { printf(%d号盘从%c移动到%c\n, n, ori, dest); return; } hanruo(n - 1, ori, dest, buf); printf(%d号盘从%c移动到%c\n, n, ori, dest);对就加了一句话printf(%d号盘从%c移动到%c\n, n, ori, dest);足以表示这个过程那之后呢这C柱也被“占领了”咋办其实C柱没有”被占“——C柱有最大号的盘子意味着这个柱可以执行任何操作——不会受到阻碍那我们就直接把C柱子看成空的就好了。那是不是和这个情况很像只不过此时满的应该是B 而不是A那不就是初始n 7的样子吗只是缓存柱子不一样了那就可以写void hanruo(int n, char ori, char buf, char dest) { if (n 1) { printf(%d号盘从%c移动到%c\n, n, ori, dest); return; } hanruo(n - 1, ori, dest, buf); printf(%d号盘从%c移动到%c\n, n, ori, dest); hanruo(n - 1, buf, ori, dest); }以oriA为缓冲柱将盘子从bufB移动到destC好了已经写完了下面就交给递归吧。或许你很惊讶——这么短好吧其实我一开始也很惊讶——我压根没打算这点代码可以跑起来但结果确实是对的我很开心#include stdio.h #include iostream using namespace std; void hanruo(int n, char ori, char buf, char dest) { if (n 1) { printf(%d号盘从%c移动到%c\n, n, ori, dest); return; } hanruo(n - 1, ori, dest, buf); printf(%d号盘从%c移动到%c\n, n, ori, dest); hanruo(n - 1, buf, ori, dest); } int main() { int n; scanf(%d,n); hanruo(n, A, B, C); }过一遍再想一遍一套流程中都干了什么第 1 步hanruo(n - 1, ori, dest, buf);把 ori 上面的n-1 个小盘借助 dest搬到 buf。重点 现在要移动的是 n-1 个盘子所以三个柱子角色发生切换起点依旧是ori辅助柱变成了dest目标柱变成了buf效果执行完这一步之后最大的第 n 号盘子孤零零留在 ori 上上面 n-1 个小盘全部挪到 buf。 此时 ori 只剩最大盘下面是空的可以移动大盘。第 2 步printf(%d号盘从%c移动到%c\n, n, ori, dest);移动第 n 号最大盘子从 ori → dest。这一步是当前层真正做的操作递归调用只是安排小盘。 大盘没有任何盘子压着目标柱 dest 现在是空或者上面盘子都比 n 号大满足规则直接移动。执行完最大盘子已经就位固定在 dest 底部之后再也不动它。第 3 步hanruo(n - 1, buf, ori, dest);把 buf 上存放的n-1 个小盘借助 ori搬到 dest。角色再次切换起点现在是bufn-1 个小盘现在在这里辅助柱变成ori现在只有那个已经移走大盘的空柱子目标柱是dest最大盘已经放在这里小盘最后叠上去效果n-1 个小盘全部移动到 dest叠在第 n 号大盘上面。 至此n 个盘子全部从 ori 移到 dest任务完成。对的这已经是一套完美的逻辑所以可以运行起来。手动演绎递归过程虽然我说得头头是道但我实际上了对这个递归的实际操作不很熟悉。所以我决定拿几个比较小的数来演绎一下过程不过一开始写的时候千万不要自己演绎容易把自己绕进去。要靠逻辑与“感觉”。n 3时接着开始递归↓再“归”↓↓↓此时1 2的进程都关闭了再继续3的进程↓这就演示完了虽然我的图可能不是很美观没办法太难画了。通过这个流程希望可以加深你的理解。