注:本文如涉及到代码,均经过Python 3.7实际运行检验,保证其严谨性。
本文阅读时间约为7分钟。
前面几节的递归算法展现了其简单而强大的一面,但是很难有一个直观的概念。
下面利用turtle库(海龟作图),通过递归做出展现递归他们的视觉影像。
作螺旋图形是递归的视觉影像应用之一。
# 递归作螺旋图形。
import turtle
t = turtle.Turtle()
def drawSpiral(t, lineLen):
if lineLen > 0: # 最小规模,0直接退出。
t.forward(lineLen)
t.right(90)
drawSpiral(t, lineLen-5) # 减小规模,即边长以减去5的速度递减。
drawSpiral(t, 100)
turtle.done()
分形树:自相似递归图形
分形(Fractal),是1975年由Mandelbrot开创的新学科。
一个粗糙或零碎的这个形状可以分成数个部分,且每一部分都(至少近似地)是整体缩小后的形状,即具有自相似的性质。下图就是一个分形图形的例子,著名的曼德博集合:
分形树:自相似递归图形
自然现象中所具备的分形特性,使得计算机可以通过分形算法生成非常逼真的自然场景。
分形,是在不同尺度上都具有相似性的事物。
利用海龟库画出分形树,把一棵树分解为三个部分:树干、左边的小树、右边的小树。
分解后,复合对递归的定义:对自身的调用。
分形树的海龟作图代码及相关解释文字如下:
import turtle
def tree(branch_len):
if branch_len > 5: # 树干太短不画,即递归结束条件。
# 第一个部分:画树干。
t.forward(branch_len) # 画树干。
t.right(20) # 右倾斜20度。
# 第二个部分:画右边的小树。
tree(branch_len - 15) # 递归调用,画右边的小树,树干减15。
t.left(40) # 向左回40度,即总体上左倾斜20度。
# 第三个部分:画左边的小树。
tree(branch_len - 15) # 递归调用,画左边的小树,树干减15。
t.right(20) # 向右回20度,即回正。
t.backward(branch_len) # 海龟退回原位置。
t = turtle.Turtle()
t.left(90)
t.penup()
t.backward(100)
t.pendown()
t.pencolor('green')
t.pensize(2)
tree(75) #画树干长度75的二叉树。
t.hideturtle()
turtle.done()
画出来的分形树如Pic-404-2所示:
To be continued.