递归应用之谢尔宾斯基三角形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()