递归应用之谢尔宾斯基三角形Python

递归应用之谢尔宾斯基三角形

谢尔宾斯基三角形，就是在一个三角形中挖掉由每条边重点组成的三角形，进而继续再新生成的三个小三角形中继续挖，如此循环。可以想象，如果无线挖下去，极限情况下，最终整个图形周长是正无穷的，面积为0。当然，也可以是立体三维图像，挖掉由每个面的中心组成的三棱锥，这样极限情况下，面积为正无穷，体积为0。

谢尔宾斯基三角形如图所示。这是一个五阶的。零阶的就是一个三角形，一阶的就是挖掉一个三角形。

其实最开始我是做不出来这道题的，看了教程，看懂了源代码。换种思路想，与其说挖掉一个三角形，不如说是用三个小三角形按照品字形组成一个大的三角形。那么这样的话，最基本的就是画三角形。需需要用到turtle库，三角形直接根据三个点的坐标绘制即可。这里传入字典，字典的key就是顶点，左边点和右边点，每个坐标就是一个元组，代表x和y。

''
例如'
points = {'left':(-200, -100),
          'top':(0, 200),
          'right':(200, -100)}
'''
def drawTriangle(points):
    t.penup()
    t.goto(points['top'])
    t.pendown()
    t.goto(points['left'])
    t.goto(points['right'])
    t.goto(points['top'])

那么接下来如何做呢？想一想只是一阶的三角形，也就是只需要画出三个小三角形即可。（当然小三角形的坐标是根据大三角形的坐标计算出来的，所以必须需要大三角形）.不难看出，小三角形的坐标就是大三角形的三个点的中点，所以需要计算中点。这里传入两个点计算。

def getMid(p1, p2):
    return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

接着继续看一阶的三角形，调用三次画三角形函数即可。

def bigTriangle(points):
	# 画最上方的三角形，需要计算坐标，不难发现，顶点就是原顶点，左边点就是原顶点和原左点的中点，右点同理。传入字典即可
	drawTriangle({
				'top':points['top'],
				'left':getMid(points['left'], points['top']),
				right:getMid(points['top'], points['right'])
				})
	# 画左边的三角形，点的坐标计算同理
	drawTriangle({
				'top':getMid(points['left'], points['top']),
				'left':points['left'],
				right:getMid(points['left'], points['right'])
				})
	# 画右边的三角形
	drawTriangle({
				'top':getMid(points['top'], points['right']),
				'left':getMid(points['left'], points['right']),
				right:points['right']
				})

那么二阶的呢？三阶的呢？不可能枚举所有的三角形。可以看出来，二阶的就是继续再新生成的小三角形里继续，也就是把新的小三角形当做零阶的继续做，三阶的同样如此，这样明显就可以用递归了。那么什么时候才画三角形呢 ？看一阶的例子，因为三个小三角形不用再挖了，所以就画了，也就是如果是0阶，那就直接画。那么如何判断当前是几阶呢，这样就需要传入一个新的参数，表示阶数，判断当前是否为0阶。

def bigTriangles(degree, points):
	# degree为阶数，如果是0阶那就直接画，否则的话，进行递归更小一阶的三角形
	if degree > 0:
		# 递归上三角形
		bigTriangles(degree - 1, 
					{ 'top':points['top'],
						'left':getMid(points['left'], points['top']),
						'right':getMid(points['top'], points['right'])})
		# 递归左三角形
		bigTriangles(degree - 1, 
					{ 'top':getMid(points['left'], points['top']),
						'left':points['left'],
						'right':getMid(points['left'], points['right'])})
		# 递归右三角形
		bigTriangles(degree - 1, 
					{ 'top':getMid(points['right'], points['top']),
						'left':getMid(points['left'], points['right']),
						'right':points['right']})
	else:
		# 否则此时为0阶，直接画三角形
		drawTriangle(points)

测试代码：

import turtle

t = turtle.Turtle()
points = {'left':(-200, -100),
          'top':(0, 200),
          'right':(200, -100)}

bigTriangles(5, points)

turtle.done()