在 python3 上使用递归的分形树

Question

我无法理解递归。 main() 函数对齐乌龟。 tree() 函数用 branchLen = 75 调用。因此，它通过 "if" 条件并上升。按照我的理解，乌龟应该连续右转5次，长度依次递减为75、60、45、30、15。之后，它就不再满足"if "条件了。代码运行只会到第 5 行（第一次递归调用）。因此，应该显示一条向 RHS 倾斜的单线。应该没有左转。但这并没有发生，一棵完全对称的树就生成了。请解释如何。
请参阅 link 以更清楚地了解问题。
谢谢！
https://interactivepython.org/runestone/static/pythonds/Recursion/pythondsintro-VisualizingRecursion.html

def tree(branchLen,t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-15,t)
        t.right(20)
        t.backward(branchLen)

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    myWin.exitonclick()

main()

Answer 1

每次调用 tree 都会记住它的位置。您是正确的，首先发生的事情是一连串的向前和向右转弯，直到 tree (0,t) 被调用。该调用不满足 if 测试，因此什么也不做。但是，这不会影响任何其他 tree 调用。因此，回到 tree(15,t)，执行从第 6 行继续，所有其他 tree 调用也是如此。

作为练习，您可以尝试在每个调用它的地方粘贴 tree 的副本，并填写 branchLen 的数字。每次调用 tree 时，实际上就是这样。

尝试 2

假设 branchLen 是函数名称的一部分，而不是参数。您将拥有一系列函数 tree75(t)、tree60、... tree0。 tree75() 将是：

def tree75(t):
    # don't need an if statement since we know 75>5
    t.forward(75)
    t.right(20)
    tree60(t)     # <-- 75-15 = 60.  Direct call to tree60().
    t.left(40)
    tree60(t)     # ditto
    t.right(20)
    t.backward(branchLen)

和除 tree0 之外的所有其他类似，它什么都不做（相当于 tree 中的 if 语句失败）。所以就像任何函数一样，tree75 调用 tree60。 tree60 从其代码的开头运行到结尾。然后 tree75 从调用 tree60 的地方继续前进：它向右转并再次调用 tree60。

就调用和 return 的行为方式而言，对递归函数的每次调用就像对任何其他函数的调用一样。不同之处在于您以特定风格编写递归函数，以便它们在调用自身时有意义。

Answer 2

你最好的理解方式是手动跟踪你调用的代码 tree(20,t)。

你应该会发现，第一次进入tree()条件是满足的，但是在两次递归调用中条件不满足，递归调用return立即到他们的调用点并继续 tree() 函数的其余部分。

要手动跟踪代码，您应该使用笔和纸记下每个执行的语句，但是当您到达对 tree() 的递归调用时，您应该继续记下语句，但缩进它们：

tree(20,t)
  if branchLen>5
  t.forward
  t.right(20)
  tree(5,t)   <--- recursive call, so start indenting next line
    if branchLen>5  <--- if fails, so return and unindent
  t.left(40)
  ...

Answer 3

不是左转。请注意如何始终使用海龟的同一个实例进行绘制，因此海龟总是从每次调用之前所在的位置继续。

def tree(branchLen,t, direction="straight"):
    if branchLen > 5:
        print branchLen, t.pos(), direction #debug info
        t.forward(branchLen)  #go forward branchlen
        t.right(20)           #rotate right 20
        tree(branchLen-15,t)  #call first branch of recursion
        t.left(40)            #rotate left 40 
        tree(branchLen-15,t)  #call second branch of recursion
        t.right(20)           #rotate right 20
        t.backward(branchLen) #go back branchlen - it is now reset to the original position before this call of tree
        print "reset to previous", t.pos()

所以本质上发生的是：

如你所料一直向右转——那是因为它向右旋转，然后进入递归的第一个分支
它从这个分支开始浮出水面，这意味着向后退到每个级别，然后调用第二个分支（这将使它在重新浮出水面之前再次'forward'，从而重复步骤 1 和 2）

您必须注意，当它浮出水面时，它开始使用调用此分支的函数的 branchLen 值，而 t 保持不变。这是调试信息的结果：

branchlen, position, direction called
75 (-0.00,-100.00) straight
60 (-0.00,-25.00) right
45 (20.52,31.38) right
30 (49.45,65.85) right
15 (75.43,80.85) right
0 (90.20,83.46) right # 0 does not draw
0 (90.20,83.46) left
reset to previous (75.43,80.85) #after this it will resurface 1 level, and repeat
15 (75.43,80.85) left
0 (85.07,92.34) right
0 (85.07,92.34) left
reset to previous (75.43,80.85)
reset to previous (49.45,65.85) #here it resurfaces twice
30 (49.45,65.85) left
15 (59.71,94.04) right
0 (69.35,105.54) right
0 (69.35,105.54) left
reset to previous (59.71,94.04)
15 (59.71,94.04) left
0 (59.71,109.04) right
0 (59.71,109.04) left
reset to previous (59.71,94.04)
reset to previous (49.45,65.85)
reset to previous (20.52,31.38)
45 (20.52,31.38) left
30 (20.52,76.38) right
15 (30.78,104.57) right
0 (40.42,116.06) right
0 (40.42,116.06) left
reset to previous (30.78,104.57)
15 (30.78,104.57) left
0 (30.78,119.57) right
0 (30.78,119.57) left
reset to previous (30.78,104.57)
reset to previous (20.52,76.38)
30 (20.52,76.38) left
15 (10.26,104.57) right
0 (10.26,119.57) right
0 (10.26,119.57) left
reset to previous (10.26,104.57)
15 (10.26,104.57) left
0 (0.62,116.06) right
0 (0.62,116.06) left
reset to previous (10.26,104.57)
reset to previous (20.52,76.38)
reset to previous (20.52,31.38)
reset to previous (0.00,-25.00)
60 (0.00,-25.00) left
45 (-20.52,31.38) right
30 (-20.52,76.38) right
15 (-10.26,104.57) right
0 (-0.62,116.06) right
0 (-0.62,116.06) left
reset to previous (-10.26,104.57)
15 (-10.26,104.57) left
0 (-10.26,119.57) right
0 (-10.26,119.57) left
reset to previous (-10.26,104.57)
reset to previous (-20.52,76.38)
30 (-20.52,76.38) left
15 (-30.78,104.57) right
0 (-30.78,119.57) right
0 (-30.78,119.57) left
reset to previous (-30.78,104.57)
15 (-30.78,104.57) left
0 (-40.42,116.06) right
0 (-40.42,116.06) left
reset to previous (-30.78,104.57)
reset to previous (-20.52,76.38)
reset to previous (-20.52,31.38)
45 (-20.52,31.38) left
30 (-49.45,65.85) right
15 (-59.71,94.04) right
0 (-59.71,109.04) right
0 (-59.71,109.04) left
reset to previous (-59.71,94.04)
15 (-59.71,94.04) left
0 (-69.35,105.54) right
0 (-69.35,105.54) left
reset to previous (-59.71,94.04)
reset to previous (-49.45,65.85)
30 (-49.45,65.85) left
15 (-75.43,80.85) right
0 (-85.07,92.34) right
0 (-85.07,92.34) left
reset to previous (-75.43,80.85)
15 (-75.43,80.85) left
0 (-90.20,83.46) right
0 (-90.20,83.46) left
reset to previous (-75.43,80.85)
reset to previous (-49.45,65.85)
reset to previous (-20.52,31.38)
reset to previous (0.00,-25.00)
reset to previous (0.00,-100.00)

Answer 4

我遇到了同样的问题。我使用了 step-by-step 策略。我画了一张图来展示我对 tree(45,t):

这个过程的想象

在 python3 上使用递归的分形树

fractal tree using recursion on python3

python

recursion

tree

fractals

尝试 2