主题：请问有关汉诺塔的递归问题！
puckery
[专家分：0] 发布于 2006-10-09 08:45:00
[em10]
请问如果我定义了一个函数：
void hanoi(int n,int a,int b,int c)
分别表示 A，B，C三个柱子！
现在用递归来运算把A柱上的N个移到C柱上，下面是函数：
void hanoi(int n,int a,int b,int c)
{
if(n>0)
{
hanoi(n,a,c,b);
printf(" move %d From %c to %c:",n,a,c);
hanoi(n,b,a,c);
}
}
我想问一下 上面的递归函数是如何实现递归的·！！
程序是如何处理的？
回复列表 （共8个回复）
沙发
boxertony [专家分：23030] 发布于 2006-10-09 10:44:00
void hanoi(int n,int a,int b,int c)
{
if(n>0)
{ // 注意：下面的两个递归第一个参数都应是n-1，否则就是死递归了
hanoi(n,a,c,b); // 先把上面的n-1个盘子从a移到b（借助c）
printf(" move %d From %c to %c:",n,a,c); // 剩下的n号盘子可直接从a移到c
hanoi(n,b,a,c); // 再把b上的n-1个盘子从b移到c（借助a）
}
}
板凳
puckery [专家分：0] 发布于 2006-10-10 09:59:00
我想请问的是，这个递归函数是如何进行递归的，如它的具体的递归步骤，如何进行交换的。
为什么只定义了一个 printf 会出现其他不同的步骤？
谢谢了 这个递归问题 困扰了我好多天啊～～～
我想知道它的具体实现的步骤啊！！
3 楼
xieyong456 [专家分：2620] 发布于 2006-10-10 11:03:00
汗，你不是在为难boxertony吗
首先递归都是从全局考虑的,因为子问题和大问题相同就可以用同样的步骤来解决,但是我们刚开始学起来的人总要去了解细节,那你就去吐血吧，你恐怕在很长一段时间内不能理解递归的奥仪...
你有C和指针这本书吗，翻到127页,里面有解释
还有你会用编辑器吗，甚至我想问你在用编辑器吗，你在用什么编辑器？
如果你在用，你就设置断点，单步执行，设置变量值，你就会明白一切
[em7][em7][em7]
4 楼
puckery [专家分：0] 发布于 2006-10-10 11:58:00
我有严的 数据结构这本书
里面一节 栈与递归的实现 中专讲这个hanoi的
但就是还不理解～～～～～～～郁闷！！！！！
5 楼
xieyong456 [专家分：2620] 发布于 2006-10-10 12:10:00
你想一步登天可能吗？
我在书上看到一句话，说的是想真正的熟练游荡于递归之间，至少要花1-2年的时间，但是值得，值得知道吗？
我想看到这个，你应该会静下来想，还是去找个好一点的编辑器，去单步执行吧
（既然你这么喜欢里面的过程），把过程记录在一个笔记本上...
[url=http://www.programfan.com/showdown.asp?id=211]http://www.programfan.com/showdown.asp?id=211[/url]
6 楼
boxertony [专家分：23030] 发布于 2006-10-10 14:36:00
[quote]为什么只定义了一个 printf 会出现其他不同的步骤？[/quote]
因为递归了呀。hanoi每调用一次自身就会有一次printf，而每一次调用自身时传递的参数都有所变化，或者是n值，或者是a,b,c值，当然就会有不同的步骤啦。
7 楼
雨523 [专家分：200] 发布于 2006-10-11 10:06:00
如果你在用，你就设置断点，单步执行，设置变量值，你就会明白一切
楼上们的这话说得极好，很有启发
在严版的数据结构上专门讲了这一节，在让系统自动实现递归的时候，利用了一个＂递归工作栈＂来保存每一个正在进行的递归步的状态信息，并依据其中的状态信息来决定下一步执行的语句．通过层层调用，回退到调用点，逐步实现整个递归操作．
如果不用系统本身的递归工作栈，就得要手动设置一个递归栈，从而出现了后面的＂利用栈实现非递归．．的算法＂
8 楼
euc [专家分：4310] 发布于 2006-10-11 20:08:00
记得严老师对递归学习方法的一总结令人印象深刻: 首先要对递归建立一种信任,相信它是能得到结果的,至于最后递归到什么时候为止最后考虑.
在读hanoi程序的时候就像注释里写的:
先把上面的n-1个盘子从a移到b（借助c）....
先从宏观上理解. 我们应该相信不管最下面的一个盘子在什么位置,上面的盘子都比它小,不受它制约.按同样的信念考虑剩下n-1个盘子,直到最上面的盘子为止.
我来回复
您所在位置：