我们在前面学习过递归函数，递归函数采用的就是递归算法，前面我们通过最常见的菲波那切数列去学习了递归函数，这一节我们再来详细了解一下递归算法。
1. 递归算法
递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念，递归算法有三个特点：
1) 递归的过程一般通过函数或者子过程来实现。
2) 递归算法在它内部来直接或者间接的调用自身的算法。
3) 递归算法就是把规模大的问题转换为规模小的问题，然后递归调用函数来求解的过程。
递归算法也有几点需要注意的事项，在前面递归函数中我们也提到过，分别是：
1) 递归是在函数本身调用函数本身。
2) 递归的效率比较低，如果有时间限制不建议使用。
3) 递归过程中需要有一个明确的结束条件，即递归出口。
2. 汉诺塔问题
汉诺塔问题也是一道十分经典的算法题目。
问题描述如下：
汉诺塔是一种古老的游戏。
一共3个柱子，标号为1,2,3。
1号柱子有从大到小一共n个盘子。
每次移动最上方的一个盘子，可以移动到其他的柱子。
任何一个盘子，都不能叠在比它更小的盘子的上方。
请把盘子从1号柱子，全部移动到3号柱子。
起始：
移动到这样：
现在，给出了n个盘子，请你描述一下用最短次数移动的过程。
我们先来分析这种三个盘子的时候的移动方式为：
->
->
->
->
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | i = 1def move(n,fr,to): global i print('这是第%d步:把%d号盘子从%s移动到%s'%(i,n,fr,to)) i += 1def hanoi(n,a,b,c): if n == 1: move(1,a,c) else: hanoi(n-1,a,c,b) move(n,a,c) hanoi(n-1,b,a,c)if __name__ == '__main__': n = int(input('输入A上面盘子的数量:')) print('移动开始') hanoi(n,'A','B','C') |
我们输入3来测试一下移动步骤与上图是否对应：
1 2 3 4 5 6 7 8 9 | 输入A上面盘子的数量:3移动开始这是第1步:把1号盘子从A移动到C这是第2步:把2号盘子从A移动到B这是第3步:把1号盘子从C移动到B这是第4步:把3号盘子从A移动到C这是第5步:把1号盘子从B移动到A这是第6步:把2号盘子从B移动到C这是第7步:把1号盘子从A移动到C |
通过结果我们可以看到和图中所示一致，注意代码中的hanoi(n,a,b,c)表示为把A根柱子上的n个盘子通过B柱子移动到C柱子上，hanoi(n-1,1,3,2)然后就要执行hanoi(n-1,2,1,3)，主要是通过这个递归函数来完成柱子的移动。
3. 总结
递归思想在我们的学习中经常会用到，如何巧妙的运用递归，可以参考一下前面递归函数中的内容。