c语言函数递归汉诺塔 c语言汉若塔输出调用递归函数次数和递归出口次数

求C汉诺塔递归过程详解

解决汉诺塔的基本思想是先把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子（初始柱子）移动到中间那个柱子上（辅助柱子），然后把最下面的盘子移动到最后一根柱子上（目标柱子）。最后把剩下的盘子移动到目标柱子上。这样，然而，完成第一步和第三步也同样是一个移动n-1个盘子的汉诺塔问题。于是，递归调用在这里不可避免。程序你已经写的很清楚，给你解释一下。现把你的程序画上行以便说明。

成都创新互联主要企业基础官网建设，电商平台建设，移动手机平台，成都小程序开发等一系列专为中小企业按需网站策划产品体系；应对中小企业在互联网运营的各种问题，为中小企业在互联网的运营中保驾护航。

1 #include "stdio.h"

2 main()

3 {void hanoi(int,char,char,char); br/4 int m; br/5 printf("input the number of disks:"); br/6 scanf("%d",m); br/7 printf("The step to moving %d disks:\n",m); br/8 hanoi(m,'A','B','C'); br/9 }

10 void hanoi(int n,char a,char b,char c)

11 {//void move(char,char);

12 if(n==1) move(a,c);

13 else

14 {hanoi(n-1,a,c,b); br/15 move(a,c); br/16 hanoi(n-1,b,a,c); br/17 }

18 }

19 void move(char x,char y)

20 {printf("%c--%c\n",x,y); br/21 }

当m=4时，程序走到第8行，调用函数hanoi(int n,char a,char b,char c)。此时，实参把值传递给了形参，于是此时，n=4,a=A,b=B,c=C。我把第11行的void move(char,char); 注释掉了，应该知道这一句的意思。因为这一行虽然可以让程序更加完整，但是解释的时候加上它会很麻烦。程序走到第12行，因为此时n=4,而不等于1，程序直接走第13行。于是调用第14行的hanoi(n-1,a,c,b)。这是一个递归调用。此时，n=3,a=A,c=B,b=C。要清楚，A，B，C代表的意义。A代表初始柱子，B代表辅助柱子，C代表目标柱子。而a代表第一根柱子,b代表第二根柱子,c代表第三根柱子。这是不一样的。程序继续走，到12行时n依然不等于1。走到14行调用hanoi(n-1,a,c,b)。此时，n=2,a=A,c=C,b=B。程序再走，到12行时n依然不等于1，走到14行调用hanoi(n-1,a,c,b)。此时，n=1,a=A,c=B,b=C。程序走到12行时发现n=1,程序开始走15行。调用move(char x,char y)到20行时输出A--B。调用结束，回到上一个调用即n=2,a=A,c=C,b=B。程序回到第15行，输出 A--B。再走第16行，调用hanoi(n-1,b,a,c)。此时n=1,b=A,a=B,c=C。程序回到12行再调用19行输出B--C。调用结束，回到上一个调用n=3,a=A,c=B,b=C。程序走到15行，输出A--C，这时，第一根柱子上有一个盘子，第二根柱子上有一个盘子，第三根柱子上有两个盘子。再调用16行就可以完成把第三根柱子里的所有盘子都移动到第二根柱子上。这样。我们就完成了整体目标的第一步。把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子（初始柱子）移动到中间那个柱子上（辅助柱子），调用完成后程序回到15行，此时n=3,a=A,c=B,b=C。15行时输出A--C，这时便完成了整体目标的第二步，最下面的盘子移动到最后一根柱子上（目标柱子）。再根据程序走到16行，经过跟14行类似的一系列的递归调用，我们就可以完成最终目标了。

求大神讲解一下C语言汉诺塔递归算法的简易理解

一开始我接触汉诺塔也是很不解，随着代码量的积累，现在很容易就看懂了，因此楼主主要还是对递归函数的理解不够深刻，建议你多写一些递归程序，熟练了自己就能理解。

圆盘逻辑移动过程+程序递归过程分析

hanoi塔问题, 算法分析如下，设a上有n个盘子，为了便于理解我将n个盘子从上到下编号1-n，标记为盘子1，盘子2......盘子n。

如果n=1，则将“ 圆盘1 ” 从 a 直接移动到 c。

如果n=2，则：

（1）将a上的n-1（等于1）个圆盘移到b上，也就是把盘1移动到b上；

（2）再将a上 “盘2” 移到c上；

（3）最后将b上的n-1（等于1）个圆盘移到c上，也就是第（1）步中放在b上的盘1移动到c上。

注意：在这里由于超过了1个盘子，因此不能直接把盘子从a移动到c上，要借助b，那

么 hanoi（n，one，two，three）的含义就是由n个盘子，从one移动到three，如果n2

那么就进行递归，如果n=1，那么就直接移动。

具体流程：

hanoi（2，a，b，c）；由于21因此进入了递归的环节中。

1执行hanoi（1，a，c，b）：这里就是刚才的步骤（1），代表借助c柱子，将a柱子上的 1个圆盘（盘1）移动到b柱子，其实由于是n=1，此时c柱子并没被用到，而是直接移动了。

2执行hanoi（1，a，b，c）：这是步骤（2），借助b柱子，将a柱子上的一个圆盘（盘2）移动到c柱子上。这里由于也是n=1，也并没有真正借助b柱子，直接移动的。

3执行hanoi（1，b，a，c）：这是步骤（3），将b上的一个盘子（盘1）移动到c

函数中由于每次调用hanoi的n值都是1，那么都不会进入递归中，都是直接执行了mov移动函数。

如果n=3，则：（倒着想会想明白）移动的倒数第二部，必然是下面的情况

（1）将a上的n`-1（等于2）个圆盘移到c上，也就是将盘1、盘2 此时都在b柱子上，只有这样才能移动最下面的盘子（盘3）。那么由于现在我们先忽略的最大的盘子（盘3），那么我们现在的目标就是，将两个盘子（盘1、盘2）从a柱子上，借助c柱 子，移动到b柱子上来，这个过程是上面n=2的时候的移动过程，n=2的移动过程是“2 个盘子，从柱子a，借助柱子b，移动到柱子c”。现在是“2个盘子，从柱子a，借助柱子 c，移动到柱子b上”。因此移动过程直接调用n=2的移动过程就能实现。

（2）将a上的一个圆盘（盘3）移到c。

（3）到这一步，由于已经将最大的盘子（盘3）移动到了目的地，此时无论后面怎么移动都不需要在用到最大的那个盘子（盘3），我们就先忽略他，剩下的目标就是将b上面的n-1个盘子（盘1、盘2）移动到c上，由于a上没有盘子了，此时要完成上面的目标，就要借助a盘子。最终达到的目标就是将b上的2个盘子，借助a移动到c上，这个过程就是当n=2时分析的过程了，仅仅是最开始的柱子（b柱子）和被借助的柱子（a柱子）不同了。所以直接调用n=2时候的过程就能股实现了。

具体执行过程：

hanoi（3，a，b，c）；由于31因此进入了递归的环节中。

1执行hanoi(2,a,c,b):这里代表刚才的步骤（1），将两个盘子（盘1、盘2）从a移动到b，中间借助c。根据n=2的分析过程，必然是能够达到我们的目的。

2执行hanoi（1，a，b，c）：现在a上只有一个盘子（盘3），直接移动到c上面即可。

3执行hanoi（2，b，a，c）：此时对应步骤（3），剩下的目标就是将b上的两个盘子，借助a移动到c上。那么同样根据n=2的移动过程，必然能达到目的。

最终实现了3个盘子从a，借助b移动到了c。

c语言用递归实现汉诺塔

见代码注释，还有不懂可以问。

#include stdio.h

void move(char x,char y)

{

printf("%c--%c\n",x,y);

}

//hannuota函数的作用：把n个圆盘从one柱子借助two柱子放到three柱子 

void hannuota(int n,char one,char two,char three)

{

if(n==1)//如果只有一个柱子 

move(one,three);//直接移动即可 

else

{

hannuota(n-1,one,three,two);//先把one柱子上的n-1个圆盘借助three柱子移动到柱子two 

move(one,three);//把第一个柱子的剩下那一个(第n个)移动到第三个柱子

//由于原来one柱子上的n-1个圆盘已经移动到了two柱子上，因此不会有圆盘挡住n圆盘出来 

hannuota(n-1,two,one,three);

//最后再把那n-1个圆盘从two柱子借助one柱子移动到three柱子

//(上面第一句话hannuota(n-1,one,three,two)已经移动到了two柱子，因此这里是从two柱子移动到three柱子) 

}

}

int main()

{

int m;

printf("input the number of diskes:");

scanf("%d",m);

printf("The step to move %d diskes:\n",m);

hannuota(m,'A','B','C');

return 0;

}