证明hanoi塔问题的递归算法与非递归算法实际上是一回事

奇妙的问题
实际上你需要形式化的描述这两种算法，才有可能证明他们是等价的吧

我比较好奇，有没有例子，证明其他某种算法的递归与非递归的等价性，很好奇这种东西是怎么证明的...
另外，参考资料里面的那只是你同学么...

证明：设解决汉诺塔问题的函数为Hanoi（n，A，B，C）
用数学归纳法即可证明上述问题
当n=1和n=2时容易直接验证。设当k<=n-1时，递归算法和非递归算法产生完全相同的移动序列。考察k=n时的情形。
将移动分为顺时针移动（S），逆时针移动（N）和非最小圆盘塔间的移动（F）三种情况。
（1）当n为奇数时，顺时针非递归产生的移动序列为S,F,S,F,······S，逆时针非递归算法产生的序列为N,F,N,F,······N。
当n为偶数时，顺时针非递归产生的移动序列为N,F,N,F,······N，逆时针非递归算法产生的序列为S,F,S,F,······S。
（2）当n为奇数时，顺时针递归算法Hanoi（n，A，B，C）产生的移动序列为
Hanoi（n-1，A，C，B）产生的移动序列，F，Hanoi（n-1，C，B，A）产生的移动序列
其中，Hanoi（n-1，A，C，B）Hanoi（n-1，C，B，A）均为偶数圆盘逆时针移动问题。由数学归纳法知，它们产生的移动序列均为S,F,S,F,······S。因此Hanoi（n，A，B，C）产生的移动序列为S,F,S,F,······S。
当n为偶数时，顺时针递归算法Hanoi（n，A，B，C）产生的移动序列为
Hanoi（n-1，A，C，B）产生的移动序列，F，Hanoi（n-1，C，B，A）产生的移动序列
其中，Hanoi（n-1，A，C，B）Hanoi（n-1，C，B，A）均为奇数数圆盘逆时针移动问题。由数学归纳法知，它们产生的移动序列均为N,F,N,F,······N。因此Hanoi（n，A，B，C）产生的移动序列为N,F,N,F,······N。
当n为奇数和偶数时的逆时针递归算法也类似。
由数学归纳法可知，递归算法和非递归算法产生相同的移动序列。