文科生快速入门python(十二) | 经典的函数递归案例

今天，数据猿重点整理了python的递归函数相关内容，递归函数是特殊的函数结构，在理解起来也相对较难，但是在个别问题上如果使用递归，将极大地简化代码，符合The Zen of Python的要求。

在python命令行中，输入import this ，即可打印python之禅

>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

本文目录如下：

image

函数与递归的关系

递归的实质：整个递归本身就是一个函数，需要函数定义描述。
函数内部使用分支语句对输入参数进行判断
递归函数的分支由基例和链条组成。基例是可以确定运算的分支，链条是进行递归的分支。

最基本的递归函数：计算阶乘


def fact(n):

    if n == 0:

        return 1

    else:

        return n*fact(n-1)

img

当然，阶乘最简单的方式是直接使用math库的factorial()函数


import math

math.factorial(n)

也可以使用for循环


def fact1(n):

    result = 1

    for i in range(1,n+1):

        if i == 1:

            result = 1

        else:

            result = i * result

    return result

fact1(6)

经典算法案例：汉诺塔问题

汉诺塔问题实际上是算法中的动态规划问题，也是经典算法题之一。

汉诺塔的来源

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

抽象化后的汉诺塔问题

有三个立柱A、B、C。A柱上穿有大小不等的圆盘N个，较大的圆盘在下，较小的圆盘在上。要求把A柱上的圆盘全部移到C柱上，保持大盘在下、小盘在上的规律（可借助B柱）。每次移动只能把一个柱子最上面的圆盘移到另一个柱子的最上面。请输出移动过程。

img

汉诺塔问题的解答

这是动态规划问题中的一种，用递归来实现较为简单方便。

我们先归纳思想来思考一下，我们乍一看难想象第一步应该怎么，我们的没经过训练的大脑，很难想象应该怎么选择每一步的操作，任意选择的话，很容易出错宕机。

所以，我们换一种归纳方式，先假设除最下面的盘子之外，我们已经成功地将上面的63个盘子移到了中介柱子B柱，此时只要将最下面的盘子由开始柱子A移动到目标柱子C即可。

img

这个时候，要想完成，我们又把A当作是目标柱子，B当作开始柱子，C当作中介柱子。

所以，对于"将n个圆盘从A柱移动到C柱（借助B柱）"这个问题，我们可以通过以下三步实现：

将A柱最上面的n-1个圆盘移动到B柱（借助C柱）。

将A柱上剩下的那1个圆盘直接移动到C柱

将B柱上的n-1个圆盘移动到C柱（借助A柱）。

汉诺塔问题的python实现

根据以上分析，我们可以得出，汉诺塔游戏的python实现代码比较简单，只需要设定好参数和基例分支、链条分支即可。

参数：包括ｎ-圆盘数量、 start、end、mid-三个柱子的名字；
分支：假设开始柱子已经剩下了最底层的那个圆盘ｎ，形成递归函数的基例，最底层以上的圆盘（ｎ－１）已经移动到中介柱子，形成递归函数的链条；
链条：最低层以上的柱子再次进行以上步骤，假设移动了最低层以上的圆盘，只剩下了最底层的那个圆盘。


count = 0

def hanoi(n: int, start: str, end: str, mid: str):

    global count  # 将count改为本module的全局变量

    # 从最下面的那个圆盘开始编写移动

    if n == 1:

        # 打印第一个圆盘的移动位置

        print('{}:{}->{}'.format(1, start, end))

        # 记录本次移动

        count += 1

    # 然后 是除了最下面圆盘之外的圆盘

    else:

        # 递归最底层以上圆盘

        hanoi(n - 1, start, mid, end)

        # 打印最底层以上圆盘的位置

        print('{}:{}->{}'.format(n, start, end))

        count += 1

        # 再次递归本次函数　通过对参数位置的改变，从而实现递归关系的链接

        # 现在的开始柱子是上一次的中介柱子，现在的目标柱子是上一次的开始柱子，中介柱子是上一次的目标柱子

        hanoi(n - 1, mid, end, start)

# 调用汉诺塔函数

hanoi(3, 'a', 'c', 'b')

print(count)

实现结果如下：

image-20210201153841038

以上可发现，最终通过7个步骤完成3个圆盘的汉诺塔游戏；

第一个圆盘，从a柱移动到b柱
第二个圆盘，从a柱移动到c柱
第一个圆盘，从b柱移动到c柱
第三个圆盘，从a柱移动到b柱
第一个圆盘，从c柱移动到a柱
第二个圆盘，从c柱移动到b柱
第一个圆盘，从a柱移动到b柱

动态展示如下：

3个圆盘的汉诺塔动态图

本项目说明

使用方法一：命令行运行


python hanoi.py [参数圆盘]

比如：


python hanoi.py 4

使用方法二：运行diaoyong_myhanoi文件调用函数

比如：


import myhanoi

myhanoi.hanoi(3, '开始', '中介', '目标')

小结

递归函数重在基例和链条的理解。基例不一定是最初的数值，在汉诺塔问题中，基例是其中的一个状态。
递归虽然简洁，但是在处理速度和理解上有些难，在编程时尽量少用，文科生只需看懂递归函数即可。

参考资料：

Leo_wlCnBlogs：汉诺塔问题.https://www.cnblogs.com/Leo_wl/p/3335388.html

菜鸟教程：Python 汉诺塔.https://www.runoob.com/w3cnote/python-tower.html

文字编辑：数据猿Riggle

首发平台：vx号：文科数据员