汉诺塔问题的递归与非递归实现

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

递归代码：

#include<stdio.h>
 
void hanoi(int n,char a,char b,char c)
{
	if(n==1) 
		printf("%c -> %c\n",a,c);       /*如果只有一个圆盘，则直接从a柱子移动到c柱子*/
	else
	{
		hanoi(n-1,a,c,b);		/*将a柱子n-1个圆盘移动到b柱子*/
		printf("%c -> %c\n",a,c); 	/*将a柱子n-1个圆盘移动到b柱子*/
		hanoi(n-1,b,a,c);		/*再把b上暂时放着的n-1个圆盘移动到c*/
	}
}
 
int main()
{
	int n;
	scanf("%d",&n);
	hanoi(n,'a','b','c');
	return 0;
}

非递归代码：

#include<iostream>
#include<stack>
using namespace std;
struct node
{
	int a,b,c,n;
	node(int m,int x,int y,int z):n(m),a(x),b(y),c(z){}
};
int main()
{
	int n;
	cin>>n;
	stack<node>s;
	s.push(node(n,'a','b','c'));
	while(!s.empty())
	{
		node t=s.top();
		s.pop();
		if(t.n==1) printf("%c -> %c\n",t.a,t.c);
		else
		{
			s.push(node(t.n-1,t.b,t.a,t.c));
			s.push(node(1,t.a,t.b,t.c));
			s.push(node(t.n-1,t.a,t.c,t.b));
		}
	}
	return 0;
}