递归算法:是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
递归过程一般通过函数或子过程来实现。
递归算法的实质:把问题不断的变小分开解决问题,洋葱一样,剥开之后里面又有一个新的整体,然后继续剥开最终把问题解决掉,(禁止套娃!)
汉诺塔是一个典型的递归算法,也比较经典下面看图。
1、将最大的上面的所用全部移动到B柱子上面也就是N-1,这里一定要把移动的部分当成一个整体
2、将A移动到C柱子上
3、将B上的移动到C上
汉诺塔基本完成,没看懂没关系,看下面解释!
下面个人认为是比较关键的思想,在第一步中提到我们必须要将B中的部分当成一个整体,然后再把B和A的位置进行交换,这样又得到了一个新的汉诺塔,然后重复这个步骤就可以了
这里我们需要注意的是当韩罗塔为一层的时候只需要一步就可以完成了,这涉及到我们思考的完备性。
hannuota(n,A,B,C):
if n==1:
print(A,'-->',C)
else:
hannuota(n-1,A,C,B)
print(A,'-->',C)
hannuota(n-1,B,A,C) //这里就是交换两个位置把B当作A形成一个新的汉诺塔