【教程】python递归三部曲（基于turtle实现可视化）-一、谢尔宾斯基三角形_递变三角形

递归三部曲：

〇、介绍递归及三原则

一、谢尔宾斯基三角形

二、汉诺塔

三、迷宫探索

1、谢尔宾斯基三角形

本教程为本人在b站投稿的视频教程对应的文字版
视频较详细，文本较简洁，大家选择一个看就好

谢尔宾斯基三角形(Sierpinski triangle),
是一种如图所示的分形
点击观看谢尔宾斯基三角形绘制动画(Sierpinski Triangle)

这里分析一下其绘制过程
1、绘制一个三角形
2、取三角形的三边中点，
以每两个中点及其所在边共有的顶点，
三个一组，组合成三个小三角形，
对三个三角形进行绘制，
如下图所示，分别为ADF，DBE，FEC。
3、对2中的三个小三角形，重复步骤2。

理论上，步骤二可以无限重复下去，但是代码而言，要保证算法的有穷性，所以一般都是将步骤二运行有限次数之后结束。

2、结合递归三原则编写代码

首先，需要添加方法draw_sierpinski来绘制指定层数的谢尔宾斯基三角形

def draw_sierpinski(triangle,depth):
	"""
	绘制指定层数的谢尔宾斯基三角形
	triangle: 指定三角形三个顶点坐标，示例：((ax,ay),(bx,by),(cx,cy))。
	depth: 指定层数
	"""
1
2
3
4
5
6

这里再解释下depth这个层数的具体意思，即上面的步骤二执行的次数
那么下图从左到右，层数分别为：0,1,2,3,4

然后我们再分析下draw_sierpinski方法应该怎么写
1，绘制三角形triangle
2，如果层数depth为0则退出递归
3，取三角形中点，及对应形成的三个小三角形，
4，对这三个三角形，分别再次调用draw_sierpinski方法，
绘制depth-1的谢尔宾斯基三角形
为了实现上面四步，我们需要添加两个辅助方法
get_midpoint(a,b) : 返回a,b两点的中点坐标
draw_triangle(a,b,c) : 以a,b,c为顶点绘制三角形
最终代码如下

#!/usr/bin/python3
import turtle


t = turtle.Turtle()


def get_midpoint(a, b):
    ax, ay = a
    bx, by = b
    return (ax + bx) / 2, (ay + by) / 2


def draw_triangle(a, b, c):
    ax, ay = a
    bx, by = b
    cx, cy = c

    t.penup()
    t.goto(ax, ay)
    t.pendown()
    t.goto(bx, by)
    t.goto(cx, cy)
    t.goto(ax, ay)
    t.penup()


def draw_sierpinski(triangle, depth):
    """
    :param triangle: 指定三角形三个顶点坐标，示例：((ax,ay),(bx,by),(cx,cy))。
    :param depth: 指定层数
    """
    a, b, c = triangle
    draw_triangle(a, b, c)
    if depth == 0:
        return
    else:
        d = get_midpoint(a, b)
        e = get_midpoint(b, c)
        f = get_midpoint(c, a)
        draw_sierpinski([a, d, f], depth-1)
        draw_sierpinski([d, b, e], depth-1)
        draw_sierpinski([f, e, c], depth-1)


if __name__ == '__main__':
    triangle = [[-200, -100], [0, 200], [200, -100]]
    draw_sierpinski(triangle, 5)
    turtle.done()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

运行效果如图

然后我们结合代码回顾一下递归三原则
如图所示：

这里补充一点，递归三原则的2和三常常是一起进行的，
即在向1中的基础情况靠拢的的情况下调用递归方法本身

3、最后补充：

问题1：没有颜色的变化
本人在b站的关于这个谢尔宾斯基三角形视频教程最终代码如步骤二中所示，但是有个小小的细节问题，就是不同层数的三角形之间没有颜色的变化，与本文开头的图一不符。所以最后还是要添加一下颜色的处理
问题2：最终运行结束后中间有黑点
大家看步骤二重最后运行效果图，中间有个黑点， 这个黑点是turtle画笔对象，一般是箭头样式，放在中间破坏了整个画面，隐藏掉就好了
解决问题一二后代码如下

#!/usr/bin/python3
import turtle


t = turtle.Turtle()
t.hideturtle()
FillColors=[
    '#CAE1FF',
    '#FFEFDB',
    '#8470FF',
    '#FF6347',
    '#FFDEAD',
    '#C1FFC1'
]


def get_midpoint(a, b):
    ax, ay = a
    bx, by = b
    return (ax + bx) / 2, (ay + by) / 2


def draw_triangle(a, b, c, depth):
    ax, ay = a
    bx, by = b
    cx, cy = c

    t.penup()
    _tcolor = FillColors[depth % len(FillColors)]

    t.color("black", _tcolor)
    t.goto(ax, ay)
    t.pendown()
    t.begin_fill()
    t.goto(bx, by)
    t.goto(cx, cy)
    t.goto(ax, ay)
    t.end_fill()
    t.penup()


def draw_sierpinski(triangle, depth):
    """
    :param triangle: 指定三角形三个顶点坐标，示例：((ax,ay),(bx,by),(cx,cy))。
    :param depth: 指定层数
    """
    a, b, c = triangle
    draw_triangle(a, b, c, depth)
    if depth == 0:
        return
    else:
        d = get_midpoint(a, b)
        e = get_midpoint(b, c)
        f = get_midpoint(c, a)
        draw_sierpinski([a, d, f], depth-1)
        draw_sierpinski([d, b, e], depth-1)
        draw_sierpinski([f, e, c], depth-1)


if __name__ == '__main__':
    triangle = [[-200, -100], [0, 200], [200, -100]]
    draw_sierpinski(triangle, 5)
    turtle.done()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

此时运行效果如图

问题3：线条重画导致粗细不一
如果有朋友观察细致的话，会发现一些边线有时有粗细不一的情况。

这是由于每次重复绘制过程的第二步时，边线也被重复绘制了，但是重复绘制有时候并不一定和原来的边线是齐的，这种反复不齐导致整个线条实际上是有多个不完全一致的线段叠起来的，所以看上去会有粗有细。

实际上，步骤二为了让大家简单直接的理解递归，所以选择了重复绘制边线这种方便递归的方法来画谢尔宾斯基三角形，方便的缺点就是重画边线导致不齐的线段叠加，当然这个缺点对于初学者完全可以忽略。

如果我们要解决这个问题，实际上就需要调整我们的绘制过程，修改原来绘制过程中的步骤二，不过这会使递归略微麻烦一点点。
具体的可看我以前博客园写的文章，这篇文章里就用的是另外一种绘制过程，来避免了重复画线：https://www.cnblogs.com/BigShuang/p/10837020.html
我就不搬运过来了。

本文主要通过三个实例来帮助大家理解递归（其展示动画已上传B站）：
谢尔宾斯基三角形(Sierpinski Triangle)
汉诺塔(Tower of Hanoi)
迷宫探索(Maze Exploring)
本文代码已上传到github：https://github.com/BigShuang/recursion-with-turtle
本文参考文献：
Problem Solving with Algorithms and Data Structures using Python
turtle官方文档：
中文：https://docs.python.org/zh-cn/3.6/library/turtle.html
英文：https://docs.python.org/3.6/library/turtle.html