在寻找任意嵌套列表的最大深度问题上

Question

我目前正在使用Python编写递归函数，并遇到了一些问题。如标题所示，问题是返回任意嵌套列表的最大深度。

以下是我的代码:

def depthCount(lst):
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.'

    var = 0

    if len(lst) > 0:

        if type(lst[0]) == list:
            var += 1
            depthCount(lst[1:])

        else:
            depthCount(lst[1:])

    else:
        return var

我觉得问题出在我的递归调用上（这可能很明显）。当列表到达末尾时，它确实会返回var，但当我有一个非空列表时，事情就会出错。根本没有返回任何东西。

我切片的方式是否不正确？在递归调用之前应该做些什么？

问题也可能出在我的基本情况上。

- user4234032

---

当if len(lst) > 0:块中没有return var时，为什么会返回某些东西？ - Navith

即使你想在 list 上进行类型切换，以便不会递归到字符串、元组、字典等中，但你真的想防止递归到 list 的子类吗？如果不是，请使用 isinstance(lst[0], list)。 - abarnert

你能否更具体地描述一下你的“嵌套列表”是什么样子？它们除了包含列表之外还包含其他内容吗？还是只有像[[[], []], [], [[]]]这样的东西？ - Stefan Pochmann

Answer 1

如果它们只是嵌套的列表，例如[[[], []], [], [[]]]，这里有一个好的解决方案：

def depthCount(lst):
    return 1 + max(map(depthCount, lst), default=0)

如果您不使用Python 3.4，这里有一个小变化可以使用，其中引入了default参数：

def depthCount(lst):
    return len(lst) and 1 + max(map(depthCount, lst))

它们的不同之处还在于计数方式。第一种方法认为空列表深度为1，而第二种则为0。不过第一种方法容易进行适应，只需将默认值设置为-1。

---

如果它们不仅仅是嵌套的列表，比如[[[1], 'a', [-5.5]], [(6,3)], [['hi']]])，则需要进行以下调整：

def depthCount(x):
    return 1 + max(map(depthCount, x)) if x and isinstance(x, list) else 0

def depthCount(x):
    return int(isinstance(x, list)) and len(x) and 1 + max(map(depthCount, x))

确保你理解后者的工作原理。如果你还不知道，它会教你如何在Python中使用and：

---

接受这个"纯递归"的挑战：

def depthCount(x, depth=0):
    if not x or not isinstance(x, list):
        return depth
    return max(depthCount(x[0], depth+1),
               depthCount(x[1:], depth))

虽然额外的参数看起来有点难看，但我认为没问题。

- Stefan Pochmann

---

是的，那也可以。基本上，你没有传递标志，而是将其更改为向下递归而不是向上递归，并将推送的深度合并到标志中。这是一个好主意；除非我试图编写尾递归代码（显然不是这种情况），否则我通常不考虑下推。但在这里这样做也没有什么不好的理由。 - abarnert

Answer 2

当列表到达末尾时，它确实会返回var，但是当我有一个非空列表时，情况就变得不对了。根本没有返回任何东西。

这是因为除了针对空列表的else基本情况外，您没有任何return语句。如果您在未命中return的情况下跌落函数，那么这意味着该函数返回None。

但是您还有另一个问题。您从var = 0开始，然后可能执行var + = 1…但是您没有将其传递到递归调用中，也没有使用任何递归调用的结果。因此，递归调用根本没有任何有用的效果。

您可能想表达的是这样的：

def depthCount(lst):
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.'

    if len(lst) > 0:

        if type(lst[0]) == list:
            return 1 + depthCount(lst[1:])
        else:
            return depthCount(lst[1:])

    else:
        return 0

但是，这样还不太对。列表的深度计数比其最深元素的深度计数多1。仅检查其第二个元素是没有用的；您需要检查全部元素。因此，你真正想要的是这样的：

def depthCount(lst):
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.'
    if isinstance(lst, list):
        return 1 + max(depthCount(x) for x in lst)
    else:
        return 0

---

如果你想用递归的方式替换迭代的 for x in lst，当然可以，但我看不出有什么好的理由这样做；这只会使代码变得更加复杂而没有任何意义。例如：

def max_child_count(lst):
    if lst:
        return max(depth_count(lst[0]), max_child_count(lst[1:]))
    else:
        return 0

def depth_count(lst):
    if isinstance(lst, list):
        return 1 + max_child_count(lst)
    else:
        return 0

---

这可能仍然不正确。它对于例如 [1, [2,3], [4, [5]]] 做了正确的事情。但是对于像 [] 这样的情况，它应该做什么？ 我从您的问题中无法得知。 如果它应该返回 0 或 1，那么您显然需要相应地更改 if 语句。如果那是非法输入，那么它已经做了正确的事情。（这应该也能回答对于例如 [[[], []], [], [[]]] 应该做什么的问题，但请确保您也仔细考虑了这种情况。）

- abarnert

---

你的第一个 depthCount() 在 [] 上失败了。ValueError: max() arg is an empty sequence。这是一个错误还是特性？ - sobolevn

@sobolevn：我不确定，你得问写作业的人。如果是个bug，当然容易修复。如果正确答案应该是0，只需将条件更改为 if isinstance（lst，list）and lst：。如果应该是其他东西，你需要做出不同的更改。 :) - abarnert

Answer 3

所以，基本上，你所提到的数据结构是一个k-ary树，也称为n元树，具有任意分支。以下是用于确定具有任意分支的n元树的最大深度的代码。

def maxdepth(tree):
    if isleaf(tree):
        return 1
    maximum = 0
    for child in children(tree):
        depth = maxdepth(child)
        if depth > maximum:
            maximum = depth
    return maximum + 1

您可以通过不同的测试输入这里查看代码的运行情况。

- Sid Shukla

---

纯递归...让我想一想。 - Sid Shukla

@Typhon：要使这个程序纯递归，你必须用递归替换_两个_循环。最易读的方法是使用两个相互递归的函数，就像我答案末尾所示。但你可能并不想这样做。 - abarnert

@SiddharthShukla：嗯，你可以使用一个标志位来有效地编码一个2状态状态机，从而只需使用一个函数来完成。但我认为这样做会使代码变得更难读懂，而不是更容易理解。 - abarnert

@StefanPochmann，说实话，我花了一个小时回复他的评论，当时他的评论只是写着“谢谢Siddharth”，后来他编辑了评论并请求提供一个纯递归函数。顺便说一句，你的解决方案很好。 - Sid Shukla

@SiddharthShukla 嗯。我相当确定在我写下这个回答时刷新了页面，它显示问题是“56分钟前”提出的，而你的回答是“48分钟前”发布的。有时候我会要求别人接受我的答案或其他人的答案，但只是因为看起来他们忘记了。比如在接下来的一天左右，如果问题已经得到完全回答，没有任何活动，而且我发现他们以前从未接受过答案。否则，我认为这可能过早了，并可能阻止其他人提供更好的答案。 - Stefan Pochmann