python - 递归调用如何工作(sierpinski 三角形)？

Question

我遇到了一个用递归绘制谢尔宾斯基三角形的程序。我如何解释这段代码是调用 sierpinski1 直到 n == 0，然后只绘制 3 个小三角形(每次调用一个三角形)，因为 n == 0 是绘制某些东西的唯一情况(panel.canvas.create_polygon) .然而，这不是代码的工作方式，因为运行时绘制的三角形数量取决于 n，而不仅仅是我认为会显示的 3 个小三角形。

有人可以向我解释当函数 sierpinski1 只有 1 个条件时可以绘制多少东西吗？那是我无法理解的程序的一部分。我查找了所有关于递归的信息，但没有任何信息可以解释为什么这种递归格式有效。

def sierpinski(n):
    x1 = 250
    y1 = 120
    x2 = 400
    y2 = 380
    x3 = 100
    y3 = 380
    panel = DrawingPanel(500,500)
    sierpinski1(n,x1,y1,x2,y2,x3,y3,panel)

def sierpinski1(n,x1,y1,x2,y2,x3,y3,panel):
    if n == 0:
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')
    else:
        sierpinski1(n-1,x1,y1,(x1+x2)/2,(y1+y2)/2,(x1+x3)/2,(y1+y3)/2, panel)
        sierpinski1(n-1,(x1+x3)/2,(y1+y3)/2,(x2+x3)/2,(y2+y3)/2,x3,y3,panel)
        sierpinski1(n-1,(x1+x2)/2,(y1+y2)/2,x2,y2,(x2+x3)/2,(y2+y3)/2,panel)

Answer 1

这是递归的工作原理:有一个基本情况和一个递归情况。由于递归使用后进先出结构(例如调用堆栈)，我们必须知道何时停止向堆栈添加调用。

基本情况:

• 在 n == 0 时发生
• 执行实际的绘画 Action
• 表示没有更多的三角形要生成了，可以开始画了。

递归情况:

• 在 n > 0 时发生(严格来说，当 n < 0 时)
• 对自身进行三个不同的调用，每个调用具有不同的 x1、x2、y1 和 y2 值。
• 意味着还有更多的三角形要生成。

可以这样想。要绘制的三角形数由公式 T 给出:

这适用于简单的三角形:如果 n = 1，则只会绘制三个三角形。如果 n = 2，则抽取 9，依此类推。

为什么会起作用？调用堆栈在其中起着重要作用。

为简洁起见，这里是 n = 1 的踪迹:

sierpinski1(n,x1,y1,x2,y2,x3,y3,panel)
    condition n = 0 FAILS
    sierpinski1(n-1,x1,y1,(x1+x2)/2,(y1+y2)/2,(x1+x3)/2,(y1+y3)/2, panel)
        condition n = 0 PASSES
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')
    sierpinski1(n-1,(x1+x3)/2,(y1+y3)/2,(x2+x3)/2,(y2+y3)/2,x3,y3,panel)
        condition n = 0 PASSES
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')
    sierpinski1(n-1,(x1+x2)/2,(y1+y2)/2,x2,y2,(x2+x3)/2,(y2+y3)/2,panel)
        condition n = 0 PASSES
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')

因此，当 n = 1 时，恰好绘制了三条线。对于 n 的更高值, 在伪代码的高层看事情变得更棘手，但同样的原则适用。