21、数据结构与算法Python:递归可视化(分形树)

递归可视化:图示

前面的种种递归算法展现了其简单而强大的一面, 但还是难有个直观的概念

下面我们通过递归作图来展现递归调用的视觉影像

*

Python的海龟作图系统turtle module

Python内置,随时可用,以LOGO语言的创意为基础,其意象为模拟海龟在沙滩上爬行而留下的足迹

  • 爬行: forward(n); backward(n)
  • 转向: left(a); right(a)
  • 抬笔放笔: penup(); pendown()
  • 笔属性: pensize(s); pencolor(c)

递归可视化:图示

import turtle
t = turtle.Turtle()

# 作图开始
t.forward(100) # 指挥海龟作图
# 作图结束
turtle.done()

*

import turtle
t = turtle.Turtle()

for i in range(4):
    t.forward(100)
    t.right(90)

turtle.done()

*

import turtle
t = turtle.Turtle()

t.pencolor('red')
t.pensize(3)

for i in range(5):
    t.forward(100)
    t.right(144)

t.hideturtle()
turtle.done()

*

一个递归作图的例子:螺旋

import turtle
t = turtle.Turtle()

def drawSpiral(t, lineLen):
    if lineLen > 0:
        t.forward(lineLen)
        t.right(90)
        drawSpiral(t, lineLen - 5)

drawSpiral(t, 100)
turtle.done()

*

分形树:自相似递归图形

自然现象中所具备的分形特性, 使得计算机可以通过分形算法生成非常逼真的自然场景

分形是在不同尺度上都具有相似性的事物

我们能看出一棵树的每个分叉和每条树枝,实际上都具有整棵树的外形特征(也是逐步分叉的)
*

这样, 我们可以把树分解为三个部分:树干、 左边的小树、 右边的小树

分解后,正好符合递归的定义: 对自身的调用
*

def tree(branch_len):
    # 树干太短不画,即递归结束条件
    if branch_len > 5:
        # 画树干
        t.forward(branch_len)
        # 右倾斜20度
        t.right(20)
        # 递归调用,画右边的小树,树干减15
        tree(branch_len - 15)
        # 向左回40度,即左倾斜20度
        t.left(40)
        # 递归调用,画左边的小树,树干减15
        tree(branch_len - 15)
        # 向右回20度,即回正
        t.right(20)
        # 海龟退回原位置
        t.backward(branch_len)

t = turtle.Turtle()
t.left(90)
t.penup()
t.backward(100)
t.pendown()
t.pencolor('green')
t.pensize(2)
# 画树干长度75的二叉树
tree(75)
t.hideturtle()
turtle.done()

*

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: