教你彻底学会递归——《进阶篇》

通过上一篇，我们已经基本了解了递归的思想，以及递归求解问题的方法。因此这一篇文章，我将通过一些经典的通过递归算法实现的实例来更深入的了解递归算法。

汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
变为数学问题：
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

整体思路就是把A柱子上的盘子分为两部分，最底下的一个盘子是一部分，剩下的盘子是一部分，那上面的例子来说就是，大号的盘子是一部分，中号和小号的是一部分，结合玩法，需要做什么呢？是不是先把中号和小号的盘子移动到B柱子上？然后在把大号盘子移动到C柱子上，最后一步就是把B柱子上的盘子全部放在C柱子上
递归的思想就是把这个目标分解成三个子目标
子目标1：将前n-1个盘子从a移动到b上
子目标2：将最底下的最后一个盘子从a移动到c上
子目标3：将b上的n-1个盘子移动到c上
然后分解目标直到n为1

代码如下：

#python
count = 0  #初始化移动次数为0
def Hanoi(n,src,mid,dest):   #给定n个盘，A柱：str，B柱：mid，C柱：dest
    global count 
    if n == 1:    #只需移动一个盘子
        print(src,"->",dest)  	#直接将盘子从str移动到dest上
        count += 1 # 移动次数加1
        return count #终止递归，返回移动次数
    else:
        Hanoi(n-1,src,dest,mid) #先将n-1个盘子从str上移动到mid
        Hanoi(1,src,mid,dest) #再将最后一个盘子从str上移动到dest
        Hanoi(n-1,mid,src,dest)	#最后将n-1个盘子从mid上移动到dest
        return count

n = int(input()) #给定盘子数
Hanoi(n,'A','B','C')  #定义n个盘子，ABC柱
print("执行次数:%d" % count)

输入样例

4

输出样例

A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
A -> C
B -> C
B -> A
C -> A
B -> C
A -> B
A -> C
B -> C
执行次数:15

通过递归方法实现归并排序

归并排序其实要做两件事：
(1) 分解：将序列每次折半拆分。
(2) 合并：将拆分开的两个序列排序后合并。

只要理解了递归的思想，就很容易实现归并排序。
图解：

代码如下：

#python
def mergesort(seq):     #归并排序
    if len(seq) <= 1:
        return seq
    mid = int(len(seq) / 2)  # 将列表分成更小的两个列表
    # 分别对左右两个列表进行处理，分别返回两个排序好的列表
    left = mergesort(seq[:mid])
    right = mergesort(seq[mid:])
    return merging(left, right)     # 对排序好的两个列表合并，产生一个新的排序好的列表

def merging(left, right):   #合并两个已排序好的列表，产生一个新的已排序好的列表
    result = []  # 新的已排序好的列表
    i = 0  # left下标
    j = 0  # right下标
    # 对两个列表中的元素 两两对比。
    # 将最小的元素，放到result中，并对当前列表下标加1
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def main():
    seq = []
    line = input().split(" ")   #输入排序数列
    for x in range(len(line)):
        seq.append(int(line[x]))
    result = mergesort(seq)     #将数列进行归并排序
    # for i in range(len(line)):
    #     print(seq[i],end=" ")
    print('\n',result)      #输出排序后的数列

if __name__=='__main__':
    main()

输入样例

8 5 4 6 1 2 3 5 12 45

输出样例

[1, 2, 3, 4, 5, 5, 6, 8, 12, 45]

到此递归算法两篇讲解结束

上一篇文章———>教你彻底学会递归——《入门篇》

下一篇文章———>pip 安装，更新，卸载模块方法