2

我可以理解简单的递归，例如：

def count(n):
    if n <= 0:
        return
    else:
        print n
        count(n-1)

count(3)

然而，当面对更复杂的代码时，比如 Koch 雪花的实现：

def koch(order, size):
    if order == 0:
            t.forward(size)
    else:
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)
            t.right(120)
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)

koch(1, 100)

我有点迷惑不解了。我不明白如何遵循这些多个递归函数调用。

4

6 回答 6

2

对于 koch(1, 100)，它将如下所示：

koch(1, 100)
->
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
    t goes left
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
    t goes right
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
    t goes left
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
<-
done

对于 koch(2, 100)，对 koch 的第一次调用将扩展到上述内容，

koch(2, 100)
->
    koch(1, 100)
    ->
        koch(0, 33)
          order == 1, so stop recursing down this branch
        <-
        t goes left
        ...
    ...
    t goes left
    ...

尝试按照建议在纸上追踪它。你最终会得到一个树状结构。

于 2013-07-19T11:54:33.460 回答
2

您的 Koch 雪花示例是一个很好的示例。雪花是由什么组成的？在第一次迭代 ( order == 0) 中，它以一条简单的线开始。这是基本情况。

________

现在，对于下一级递归 ( order == 1)，该基本情况被分成四个子行，形成一个反转的V。要实现这一点V，您需要以适当的角度构建四条线（为此您需要t.left(60)和类似的命令）。

这些行中的每一行（就其本身而言）同样是基本案例的一个实例。它只小了三倍。这就是你在koch(order-1, size/3).

   /\
__/  \__

现在想象下一层递归——每一行又被分成四个子行。模式还在继续……

于 2013-07-19T11:48:17.620 回答
2

我不认为任何人都特别容易在他们的脑海中详细地可视化执行路径。绘制一棵树，其节点代表各个递归调用，是在纸上可视化它的好方法。如果每个节点都是一个气泡，您可以在其中放入有关变量状态等的信息。在有多个递归调用的情况下，每个节点下面会有多棵树，代表一个时间线。

于 2013-07-19T11:41:54.077 回答
1

Try, something along the lines of:

def koch(order, size):
    print 'koch(', order, size, ')'
    if order == 0:
            t.forward(size)
            print 'Got to the bottom of it'
    else:
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)
            t.right(120)
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)

koch(1, 10)

And you should see how each call calls koch until it finally gets to the bottom of the chain.

于 2013-07-19T11:43:46.073 回答
1

python 导师网站可以帮助可视化程序流程 http://www.pythontutor.com/

于 2013-07-19T12:09:18.740 回答
0

要了解代码，看看创建科赫雪花的第一步会有所帮助。在每个递归步骤中，您都有一个三角形，一个代码覆盖另一个。现在你有了新的三角形，代码被调用了——一切都从头开始。

于 2013-07-19T11:45:14.393 回答