文档介绍：: .
汉诺塔递归与非递归算法研究
作者1,作者2,作者33
（陕西师范大学计算机科学学院，陕西西安7到B上。
(2)将A上的一个圆盘移到Co
(3)将B上的n-2(等于1)个圆盘移到Co
B)将A上的一个圆盘移到Bo
C)将C上的n-1(等于2)个圆盘移到B(借助A),步骤如下：
(1)将C上的n-2(等于1)个圆盘移到A。
(2)将C上的一个盘子移到Bo
(3)将…的n-2(等于1)个圆盘移到Bo至ij此，完成了三个圆盘的移动过程。
从上面分析可以看出，当n大于等于2时，移动的过程可分解
为三个步骤：
第一步把A上的n-1个圆盘移到C上；第二步把A上的一个圆盘移到B上；第三步把C上的n-1个圆盘移到B上；其中第一步和第三步是类同的。
算法如下：(伪码描述、自然语言描述、流程图)
Main
1: {intn;
2: Input(n);
3: Hanoi(n,“A“，“B";}“C)
4: Hanoi(n,chara,charb,charc)
5: {if(n>0)
6: {hanoi(n-1,a,c,b);
7: printf"(%d%n"，na,c);
8: hanoi(n-1,b,a,c);}
}
递归算法结构清晰，可读性强，而且很容易用数学归纳法证明算法的正确性，然而它的运行效率较低，它的时间复杂度主要在程序嵌套调用所用的时间。T(N)=2T(N-1)+1,容易
计算出T(N)=2N-，使其转化为非递归调用算法。通常，消除递归采用一个用户定义的栈来模拟系统的递归调用工作栈，从而达到递归改为非递归算法的目的。
非递归1:遍历二叉树搜索解空间(三级标题小五楷体)通过定义MAXSTACK栈，可将递归算法转化为非递归调
用算法。具体程序如下：
#defineMAXSTACK100/*栈的最大深度*/
intN=3;/*N阶问题/*
intc=1;/*一个全局变量，表示目前移动的步数*/structhanoi{/*存储汉诺塔的结构，包括盘的数目和三个盘的名称*/
intn;chara,b,c;};
structhanoip[MAXSTACK];
voidmove(chara,intn,charc)/*移动函数，表示把某个盘从某根针移动到另一根针*/
{printf("%%dfrom%cto%c\n",c++,n,a,c);}voidpush(structhanoi*p,inttop,chara,charb,charc,intn){p[top+1].n=n-1;
p[top+1].a=a;
p[top+1].b=b;p[top+1].c=c;}
voidunreverse_hanoi(structhanoi*p)/*汉诺塔的非递归算法*/{inttop=0;
while(top>=0){
while(p[top].n>1){/*向左走到尽头*/push(p,top,p[top].a,p[top].c,p[top].b,p[top].n);to