希尔伯特曲线分析

Question

我刚开始学习Python，但我不太明白为什么一个函数可以在自己里面调用自己。

这里有一个例子：

import turtle
from turtle import left, right, forward

size = 10

def hilbert(level, angle):
    if level == 0:
        return

    turtle.color("Blue")
    turtle.speed("Fastest")

    right(angle)
    hilbert(level - 1, -angle)
    forward(size)
    left(angle)
    hilbert(level - 1, angle)
    forward(size)
    hilbert(level - 1, angle)
    left(angle)
    forward(size)
    hilbert(level - 1, -angle)
    right(angle)

这个到底是怎么回事呢？

谢谢。

Answer 1

这是一种强大的编程技巧，叫做递归。它的意思是把一个大问题拆分成几个相似但更小的问题，直到你把问题缩小到一个可以轻松解决的程度。

Answer 2

当 level 等于 0 时，调用 hilbert(level,angle) 这个函数其实什么都不做，直接返回。

接下来看看当 level 等于 1 时会发生什么：调用 hilbert(1,angle) 会执行以下这些操作：

turtle.color("Blue")
turtle.speed("Fastest")
right(angle)
forward(size)
left(angle)
forward(size)
left(angle)
forward(size)
right(angle)

我觉得这可能是在画一个正方形的三条边。

这里的 hilbert(level-1,...) 语句被去掉了，因为 level-1 等于 0，而我们已经知道 hilbert(0,...) 是不做任何事情的。

然后，想想当你调用 hilbert(1,-angle) 时会发生什么。接着，再考虑当 level 等于 2 时会怎样。我希望这能给你一些思路，帮助你继续往下理解。

顺便说一下，Python 的一个好处是，你可以通过交互式的方式运行程序，看看调用 hilbert(1,angle) 时发生了什么，然后再看看 hilbert(2,angle) 时又会怎样，等等……

Answer 3

我无法接受递归的美妙之处在于不理解它，也无法接受我可能自己也理解不了它这个事实！所以在咨询了一个朋友之后，我终于明白了栈是怎么工作的。以下是我写的代码，展示了如果层级(level)为2，角度(angle)为90°时的空间填充希尔伯特曲线：

import turtle
from turtle import left, right, forward

size = 10
angle = 90

turtle.hideturtle()
turtle.color("Blue")
turtle.speed("Fastest")

''' Assume we have two levels. '''

right(angle)

# 1st hilbert call
right(-angle)
forward(size)
left(-angle)
forward(size)
left(-angle)
forward(size)
right(-angle)

# Continue from first call of hilbert
forward(size)
left(angle)

# 2nd hilbert call
right(angle)
forward(size)
left(angle)
forward(size)
left(angle)
forward(size)
right(angle)

# Continue from second call of hilbert
forward(size)

# 3rd hilbert call
right(angle)
forward(size)
left(angle)
forward(size)
left(angle)
forward(size)
right(angle)

# Continue from third call of hilbert
left(angle)
forward(size)

# 4th call of hilbert
right(-angle)
forward(size)
left(-angle)
forward(size)
left(-angle)
forward(size)
right(-angle)

# Continue from fourth call of hilbert
right(angle)

太棒了！