递归与分形

上一课的 draw_y 只分叉一次。真树不是这样：粗枝再分细枝，细枝再分更短的枝，直到短得不必再分。整体和局部长得像，这叫 分形。

若按每一根枝条去写 forward，程序会随层数爆炸。另一条路是：把「画一段，再在两侧画更小的同类形状」写成一个 函数，并让它在执行中调用自己。这叫 递归。

递归必须有退出条件，否则会一直分叉下去；画完后必须把 海龟 的位置与朝向还原，外层才能从分叉点画另一侧。

环境仍是 在线 IDE。默认朝东，向上长树先左转 $90^\circ$。

罗马花椰菜的每一朵小花，都像整棵菜的缩影：螺旋、锥体、再套一层更小的螺旋。把一朵小花摘下来，结构并不变成另一种蔬菜，只是尺度变了、可再分的层数变少了。

1970 年代，本华·曼德博用 fractal 这个词去命名一类欧几里得长度很难量准的对象。海岸线是他常用的例子：尺子越短，量到的弯曲越多，测得的长度就越长——不是海岸「变长了」，而是测量进入了更细的层次。

程序里的分形树比罗马花椰菜更干净：左右枝由同一条规则生成，缩短比例是明确的数，层数是明确的整数。可以这样设想：画一段，再在末端分两叉；停下是因为「已经太短」或「层数已经用尽」。重复同一规则、直到满足停止条件——这正是递归的结构。

分形 首先是关于对象的说法：把它的一部分放大，仍能看见和整体相像的结构。本课的树在每一段枝的末端再分出两段更短的枝。生成局部的过程，与生成整体的过程是同一个。

这与「把矩形重复铺满地面」不同。地砖的重复是平移，尺度不变；分形的重复带着缩放：下一层更短、往往也更转。因此，复杂并不等于程序很长——看起来枝叶纷繁，可能只是同一句「再分两叉」执行了四、五层。

数学理想可以无限分下去；屏幕和海龟只能画到某一层。把层数 $n$ 写进程序，就是把「量到哪一档」变成可执行的判断。$n=1$ 是 Y，$n=2$ 是 Y 的两臂上再各有一个 Y，$n=4$ 已经像一棵示意性的树。

循环 在同一层环境里重复：把同一件事做 $k$ 遍。海龟若只用循环画正方形，四次前进发生在同一次执行里。

递归 是函数在执行时调用自己。每一次调用都是一次新的、独立的执行：有自己的参数。写的是同一个名字，跑起来是一层新的现场。内层结束之后，外层从打断的地方继续。

两件配套的事缺一不可：

• 退出条件：例如 $n = 0$，不再画、不再调用自己。
• 递归步骤：把问题收成「更小的同类问题」，再调用自己去解。对树而言，长度乘以小于 $1$ 的比例，并且 $n$ 减 $1$。

没有退出条件，调用会一直叠下去。循环与递归都能导致「停不下来」，差别在于现场是否分层：循环只有一层姿态在被改写；递归每一层都有自己的 length 与 $n$，也因此每一层都必须自己负责把海龟送回家。

选哪一种，看问题的形状：对象里面还是同类对象时，递归更接近思想；把名单上的每一项做一遍时，循环更直白。

把上一课「亲手画出的两枝」换成「请函数自己去画两棵更小的树」。层数 $n$ 每深入一次减 $1$，长度乘 $0.7$。左转、右转、退回的角度与 draw_y 相同——姿态纪律没有变。

import turtle

t = turtle.Turtle()
t.left(90)


def draw_tree(length, n):
    if n == 0:
        return
    t.forward(length)
    t.left(30)
    draw_tree(length * 0.7, n - 1)
    t.right(60)
    draw_tree(length * 0.7, n - 1)
    t.left(30)
    t.backward(length)


draw_tree(80, 4)

$n=1$ 时，两次内层调用立刻因 $n=0$ 返回，画出来的就是一个 Y。$n$ 增大，Y 的两臂上再长出 Y。可在 在线 IDE 中先用 $n=2$ 看清结构，再增到 $3$、$4$。

以 draw_tree(80, 2) 为例：写的是同一个名字，跑起来是一次新的执行。外层画主干后，左转调用左子树；左子树画完并还原姿态后，右转再画右子树；最后后退回到起点。

若漏掉最后的后退，右子树会从错误的位置长出。若漏掉内层的后退，错误会被放大：每一层都把下一层接到叶尖上。递归能叠层，是因为每一层都把自己造成的位移撤回去。

在 在线 IDE 里先 import turtle，建立海龟并 left(90)，让它朝北。再写 draw_antenna(length, n)，并用 draw_antenna(80, 3) 调用一次。条件如下：n == 0 时直接返回；否则前进 length，左转 $45^\circ$，以 length * 0.6 和 n - 1 递归画左枝，退回并右转 $45^\circ$ 恢复朝向，再右转 $45^\circ$，以同样的缩短比例画右枝，退回并左转 $45^\circ$ 恢复朝向，最后 backward(length)。跑完后海龟应停在起点，朝向仍朝北。

• 分形把「整体像局部」说成几何；同一条生成过程作用在更小的尺度上。复杂来自规则的深度，不是来自程序的篇幅。
• 递归不是另一种循环。循环在同一层重复；递归每次进入新的执行，把问题交给更小的同类问题。
• 递归必须有退出条件，否则自己调用自己不会停。退出条件是尺度选择：模型在哪一档以下不再声称成立。
• 画树时，递归步骤是：调用自身画更小的子树，并且回到原位。忘记还原姿态，下一侧会接到错误的世界上。