证明hanoi塔的递归算法和非递归算法,用递归法求汉诺塔问题Python
在学习递归的时候，很多朋友对汉诺塔的递归算法非常困惑。他们不知道为什么这么复杂的移动过程，用四五行代码就解决了。汉诺塔问题：有A、B、C、B、C三根柱子，A柱上有若干个盘子，每次移动一个盘子，小的只能叠在大的上面。把所有盘子从A栏移到c栏。
我从一个非常直观的角度，用示意图来说明汉诺塔的python递归程序实际上是如何一步步分解的。
它在跑。
我来说几个理解上的关键点【很关键】:
(1)递归。说白了，默认定义的功能，不用考虑具体的实现细节，就能实现想要的功能，然后
不断调用这个函数，可以类比高中的数学归纳法来理解，只不过归纳法是从小到大，递过来的。
从大到小。
(2)前n-1个盘操作时，最下面的第N个盘可视为地，因为第N个盘高于前面的第n-1个盘。
所有的磁盘都很大。同样，如果要移动前n-2个磁盘，那么可以将n-1，n个磁盘视为地面。
(3)对于函数move(n，A，B，C)来说，里面的参数A，B，C都是变量，它们的名字是什么并不重要，
如下图所示，不变的是参数对应的位置。
准确的说，move()函数的格式应该是：move(n，位置1，位置2，位置3)。
例如，move(n，A，B，C)表示将n块板从对应于第一个位置参数的列移动到第三个位置。
对应于参数的列。同理，那么move(n，B，A，C)就是n个磁盘从B列移动到C列。
让我们看看下面的python程序：
定义的函数是move(n，A，B，C)，默认情况下，该函数可以实现“将所有N个磁盘从a柱移动到C”
列”这个操作。然后从N向后推一步(即如何将底部最大的板块从A列移到C列)。注意这里。
前一步不是指某个具体的前一步，而是一个一般的、整体的前一步。在初始状态下，前n-1块板从A列移动到B列，对应的函数move(n-1，A，C，B)将A列底部的第n块板移动到目标列：C列将B列的前n-1块板移动到C列，对应的函数move(n-1，B，A，C)
这里肯定有人会疑惑，“将B列前n-1块板整体移动到C列”的操作是怎么做的？
让我们回到定义的函数move(n，A，B，C)，它可以实现“将所有N个磁盘从a柱移动到C”
列”这个操作，我们不管它是怎么做的，只要定义这个操作对应的move()函数就可以了。
，并假设这个操作可以实现。
然后，上面的步骤1“将前n-1个板从列A移动到列B”，这由函数move(n-
1，A，C，B).Step1完成后，a列第n块板上没有板了，此时Step2可以把第n块板放到a列底部。
孔板(最大的孔板)移动到最终目标列C列。
接下来，第3步“将B列上的前n-1块板移动到C列”，这由函数move(n-1，B，A，C)表示。至此，总的来说，这个运动完成了。
接下来，具体解释一下这个递归程序是如何工作的：
n=1的情况很好理解。直接把这个盘子从A列移到c列就行了。
N1，程序首先执行else中的第一个函数move(n-1，A，C，B)。让我们看看move(n-1，A，C，B)
它是如何实现的：
让我们回顾一下开头提到的要点：
即在开头定义的move()函数框架下，当执行move(n-1，A，C，B)函数时，确实可以实现“将前n-1个板块从A列移动到B列”的操作。
对于函数move(n-1，A，C，B)，如果n-11，else分支中的第一个函数还是应该先执行。
移动(n-2，A，B，C).
.
以此类推，直到n-k=1，即move函数中表示板数的参数为1，然后程序开始执行。
行真正意义上的第一步是操作print (a，-，c)，但需要注意的是，这里的a和c只代表move()函数。
对应于第一位置参数的柱上的塔板移动到对应于第三位置参数的柱上的塔板，如果
函数move(1，B，A，C)，然后打印(B，-，C)，如果函数move(1，B，C，A)，则打印(B，-，A)。
move(1，position 1，position 2，position 3)的执行步骤已经知道，所以move(2，position 1，position
2，位置3)也是已知的。以move(2，A，B，C)为例【注：实际运行时的move()函数
1，2，3的位置正好对应哪根柱子，程序会自行计算)]，move(2，A，B，C)程序为：
至此，move(2，position 1，position 2，position 3)的具体执行步骤已经知道。
同理，移动(3，位置1，位置2，位置3)甚至移动(n-1，位置1，位置2，位置3)
3)的执行步骤都是已知的。这时，我们来看看原程序：
else分支下的move(n-1，A，C，B)和move(n-1，B，A，C)函数的具体执行步骤都是已知的。
至此，move (n，A，B，C)的整个执行步骤都清晰了。
如果你还有疑问，请留言。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。