利用Python实现递归算法可视化

红太狼 2021-09-07 06:15 516阅读 0赞

## 利用Python实现递归算法可视化 ##

**递归算法可视化有利于我们更清晰的理解递归算法。**

这个其实是转载的 我在另一个网站上面写的文章，应网站要求，标为转载啦~~~~~

在本文中，首先介绍递归函数以及递归算法的思想，然后，我们将利用Python来实现递归函数的可视化。

## 一、递归函数（递归算法）简介 ##

递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

**另外，递归一定要有结束的条件。**

## 二、递归可视化的实现方法 ##

Python中自带有turtle模块，该模块是Python自带的绘图工具，因此我们可以利用该模块（turtle）来实现递归算法的可视化。

再次强调一下，递归算法可视化有利于我们更清晰的理解递归算法，这种方法也十分直观。

## 三、具体案例的实现 ##

## 案例一 ##

**绘制二叉树**  
在本例中，我们将利用turtle模块来实现二叉树的可视化。

import turtle
    # 导入库（turtle）
    
    
    def __draw__tree__(tur_0, step_0, arg_0):
        """ 二叉树的可视化实现 通过递归算法来实现二叉树的绘制 :param tur_0: 一个 turtle 对象 :param step_0: 设置前进的像素 :param arg_0: 设置旋转的角度 :return: 空（无返回值） """
        if step_0 > 80:  # 递归的结束条件！！
            # 绘制一个二叉树的一个小单元
            tur.right(arg_0)
            # 右转
            tur.forward(step_0)
            # 前进
            __draw__tree__(tur_0=tur_0, step_0=step_0-20, arg_0=arg_0)
            # 调用自身，实现递归算法
            tur.back(step_0)
            # 后退
            tur.left(2 * arg_0)
            # 左转
            tur.forward(step_0)
            __draw__tree__(tur_0=tur_0, step_0=step_0 - 20, arg_0=arg_0)
            tur.back(step_0)
            tur.right(arg_0)
        else:
            pass
    
    
    if __name__ == '__main__':
        """ main 函数 """
        step = 160
        # 设置前进的像素
        arg = 24
        # 设置旋转的角度
        tur = turtle.Turtle()
        # 定义 turtle 对象
        tur.speed(5)
        # 设置turtle对象的移动速度
        tur.up()
        # 抬起turtle对象，不绘制图像
        tur.right(90)
        tur.forward(200)
        tur.right(180)
        tur.down()
        # 发下turtle对象，绘制图像
        tur.pensize(3)
        # 设置绘制图像的粗为3个像素
        tur.pencolor('green')
        # 设置绘制的图像为绿色
        __draw__tree__(tur, step, arg)
        # 调用函数
        turtle.done()
        # 使画面静止住

运行结果展示如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center]

## 案例二 ##

**绘制“雪花”**  
在本例中，我们将上一个例子进行改进绘制一个n叉树  
注意此例中有一个需要输入的数值！！

import turtle
    
    
    def __draw__(t, a, s, n, num):
        """ 实现n叉树的绘制 :param t: turtle对象 :param a: 设置：旋转的角度 :param s: 设置：运动的像素 :param n: n叉树中的数值：n :param num: 每次，缩减为原来的运动的像素的num分之一 :return: 空（无返回值） """
        if s > 20:  # 递归结束的条件
            # 实现绘制
            t.right(180 - a / 2)
            for i in range(n):
                t.forward(s)
                __draw__(t=t, a=a, s=s / num, n=n, num=num)
                # 每次，缩减为原来的运动的像素的num分之一
                t.back(s)
                t.right(a)
            t.left(180 - a / 2)
        else:
            pass
    
    
    if __name__ == '__main__':
        """ main 函数 """
        n = int(input('please input the number of the dimension you want the project to draw the picture : '))
        # 输入 n 叉树的 n 值
        arg = 360 / n
        # 将转角计算出来
        step = 160
        # 设置运动的像素
        num = 2
        tur = turtle.Turtle()
        tur.pensize(3)
        tur.pencolor('#970c0c')
        # 颜色的 RGB 值
        __draw__(tur, arg, s=step, n=n, num=num)
        # 调用函数
        turtle.done()
        # 使画面静止

注意此例中有一个需要输入的数值！！  
运行结果展示如下：  
结果一：（3）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 1]

结果二：（4）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 2]  
结果三：（6）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 3]

## 案例三 ##

**无穷三角形  
（Koch三角形的可视化）**  
解释Koch三角形：

科赫曲线是一种分形。其形态似雪花，又称科赫雪花、雪花曲线.瑞典人科赫于1904年提出了著名的“雪花”曲线，这种曲线的作法是，从一个正三角形开始，把每条边分成三等份，然后以各边的中间长度为底边。分别向外作正三角形，再把“底边”线段抹掉，这样就得到一个六角形，它共有12条边。再把每条边三等份，以各中间部分的长度为底边，向外作正三角形后，抹掉底边线段。反复进行这一过程，就会得到一个“雪花”样子的曲线。这曲线叫做科赫曲线或雪花曲线。  
具体实现：

import turtle
    import numpy as np
    
    
    def draw_Koch_Triangle(turtle_00, step):
        """ 绘制Koch三角形 :param turtle_00: turtle对象 :param step: 前进的像素 :return: 空 """
        if step > 420 / 3 / 3 / 3 / 3:  # 结束递归的条件
            # 绘制Koch三角
            draw_Koch_Triangle(turtle_00, step / 3)
            # 调用自身实现递归
            turtle_00.right(60)
            draw_Koch_Triangle(turtle_00, step / 3)
            # 调用自身实现递归
            turtle_00.left(120)
            draw_Koch_Triangle(turtle_00, step / 3)
            # 调用自身实现递归
            turtle_00.right(60)
            draw_Koch_Triangle(turtle_00, step / 3)
            # 调用自身实现递归
        else:  # 递归结束时进行的操作
            turtle_00.forward(step)
            turtle_0.right(60)
            turtle_00.forward(step)
            turtle_0.left(120)
            turtle_00.forward(step)
            turtle_0.right(60)
            turtle_00.forward(step)
    
    
    if __name__ == '__main__':
        """ main 函数 """
        screen = turtle.Screen()
        # 设置屏幕
        turtle_0 = turtle.Turtle()
        screen.title(" Koch Triangle")
        # 设置屏幕的名称为： Koch Triangle
        turtle_0.shape("arrow")
        # 设置turtle对象的形状为arrow
        turtle_0.speed(10)
        turtle_0.right(30)
        turtle_0.penup()
        # penup 和 up 是一样的
        turtle_0.forward(70 * np.sqrt(3))
        # 等边三角形与根号3有关的，因此利用数学库实现根号3的计算得值
        turtle_0.pendown()
        # pendown 与down 是一样的
        turtle_0.left(150)
        turtle_0.penup()
        turtle_0.forward(420 / 3)
        turtle_0.pendown()
        for i in range(6):
            turtle_0.right(60)
            draw_Koch_Triangle(turtle_0, 420 / 3 / 3)
            turtle_0.left(120)
            draw_Koch_Triangle(turtle_0, 420 / 3 / 3)
        turtle.done()

运行结果展示如下所示：  
（在这里我修改了绘制的次数，因此有不同的结果，你也可以自行修改递归结束条件来改变绘制的次数哦~~~）  
结果1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 4]  
结果2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 5]  
结果3：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 6]  
结果4：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 7]

我们也可以从以上的结果中看出来，Koch三角形最终是趋向于一个固定的图形的，实际上，Koch三角形的面积是有限的（虽然整个图形是无限的），但是其周长又确实是无限的，大家有兴趣的话可以自己用数学方法进行计算和证明。

**综上所述，以上便是我们的递归可视化的部分案例，希望以此来帮助大家更好地理解递归算法~~~**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center]: /images/20210813/f01ca3a7785d42ea9e8bdf5b02157ce0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210813/49ee82666d664b72a8cbc7e81a9979ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210813/fc9b5402fc7d4919893c8540e8826141.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210813/64fe1999ce1a48dca7b7c49f7e24707f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210813/55e10e913eb141e68632c8bcb7d976dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210813/53ef3243397f41c78d76241b9cab39aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20210813/6b6bd125462a4fa7b80984ce1b3445e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU0MjE4MjYz_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20210813/bb8d7fc5a8fd4d4c9d1ee05732e76aa7.png