数据结构与算法(Python版)二十一：递归可视化（分形树）

递归可视化：图示前面的种种递归算法展现了其简单而强大的一面，但还是难有个直观的概念下面我们通过递归作图来展现递归调用的视觉影像Python的海龟作图系统turtle modulePython内置，随时可用，以LOGO语言的创意为基础，其意象为模拟海龟在沙滩上爬行而留下的足迹爬行： forward(n); backward(n)转向： left(a); right(a)抬笔放笔： penup();

亥虫

7740人浏览 · 2020-06-23 10:56:06

亥虫 · 2020-06-23 10:56:06 发布

递归可视化：图示

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

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

在这里插入图片描述

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()