0

我刚开始学习递归，我有一个任务要编写一个程序来告诉列表的嵌套深度。好吧，我四处浏览并找到了执行此操作的工作代码，但我仍然无法理解它是如何工作的。这是代码：

def depth(L) :
    nesting = [] 
    for c in L:
        if type(c)  == type(nesting) :
            nesting.append(depth(c)) 
    if len(nesting)  > 0:
        return 1 + max(nesting)
    return 1

所以很自然，我开始对调用递归的追加感到困惑。有没有人有一个简单的方法来解释这里发生了什么？我不确定实际附加了什么，并且在我的脑海中使用测试用例进行检查并没有帮助。谢谢！

编辑：抱歉，如果格式不好，我是用手机输入的

4

4 回答 4

2

让我以简单的方式向您展示，更改代码如下：（### 是我添加到您的代码中的新行，以便您可以看到那里发生的事情）

def depth(L) :
    nesting = []
    for c in L:
        if type(c)  == type(nesting) :
            print 'nesting before append', nesting ###      
            nesting.append(depth(c))
            print 'nesting after append', nesting ###
    if len(nesting)  > 0:
        return 1 + max(nesting)
    return 1

现在让我们制作一个深度为三的列表：

l=[[1,2,3],[1,2,[4]],'asdfg']

你可以看到我们的列表有 3 个元素。其中一个是一个列表，另一个是一个列表，它本身有另一个列表，最后一个是一个字符串。可以清楚的看到这个列表的深度是3（即主列表的第二个元素有2个列表嵌套在一起）

让我们运行这段代码：

>>> depth(l)
nesting before append []
nesting after append [1]
nesting before append [1]
nesting before append []
nesting after append [1]
nesting after append [1, 2]
3

小菜一碟！此函数将 1 附加到嵌套中。然后如果该元素还有另一个列表，它会附加 1 + 嵌套中的最大数量，这是时间函数本身被调用的数量。如果元素是字符串，则跳过它。

最后，它返回嵌套中的最大数量，即递归发生的最大次数，即主列表中列表中存在列表的次数，即深度。在我们的例子中，第二个元素 + 1=3 的递归发生了两次，正如我们预期的那样。

如果您仍然无法获取它，请尝试print在函数中添加更多语句或其他变量并仔细观察它们，最终您会得到它。

于 2013-04-24T17:47:55.873 回答
1

让我们从几个例子开始。

首先，让我们考虑一个只有一层深度的列表。例如，[1, 2, 3]。

在上面的列表中，代码以调用depth()with开始L = [1, 2, 3]。它生成一个空列表nesting。遍历Lie的所有元素，1, 2, 3并没有找到通过测试的单个元素type(c) == type(nesting)。检查len(nesting) > 0失败并且代码返回 1，这是列表的深度。

接下来，我们举一个深度为 2 的例子，即[[1, 2], 3]。depth()调用该函数L = [[1, 2], 3]并创建一个空列表nesting。该循环遍历 L ie 的 2 个元素，[1, 2] , 3并且因为type([1, 2]) == type(nesting),nesting.append(depth(c))被调用。与前面的例子类似，depth(c)即depth([1, 2])返回一个 1nesting现在变成[1]。循环执行后，代码评估测试len(nesting) > 0结果True和返回1 + max(nesting)结果。1 + 1 = 2

类似地，深度 3 的代码如下，依此类推。

希望这会有所帮助。

于 2013-04-24T17:41:45.300 回答
1

所以这似乎是一个函数，它接受一个列表并计算，正如你所说的，它的嵌套深度。嵌套是一个列表，所以if type(c) == type(nesting)说的是：如果列表中的项目L是一个列表，则再次运行该函数并附加它，当它再次运行该函数时，它将执行相同的测试，直到列表中没有更多的嵌套列表L然后返回 1 + 嵌套列表的最大数量，因为每个列表的深度都是 1。

请告诉我是否有任何不清楚的地方

于 2013-04-24T17:29:00.557 回答
0

该算法访问嵌套列表并为每一级递归添加一个。调用链是这样的：

depth([1, 2, [3, [4, 5], 6], 7]) =
    1 + depth([3, [4, 5], 6]) = 3
        1 + depth([4, 5]) = 2
            1

由于 depth([4,5]) 永远不会进入if type(c) == type(nesting)条件，因为没有元素是列表，它从外部返回返回 1，这是基本情况。

在这种情况下，对于给定的深度，您有多个嵌套列表，例如[1, [2, 3], [4, [5, 6]]，最大深度[2,3]和[4, [5, 6]]都附加在深度调用上，其中最大值由内部返回返回。

于 2013-04-24T17:36:16.930 回答