处理Python中嵌套列表长度计算中的递归和错误情况

Question

我正在创建递归函数的改进版本，以计算处理最大递归深度和潜在错误情况的嵌套列表的长度。

def recursive_list_length(items, depth=0):
    if not isinstance(items, list):
        return 1
    elif depth > 10:
        raise RecursionError("Maximum recursion depth exceeded")

    total_count = 0
    for item in items:
        if isinstance(item, list):
            try:
                total_count += recursive_list_length(item, depth + 1)
            except RecursionError as e:
                print(f"Recursion error occurred at depth {depth + 1}: {e}")
        else:
            total_count += 1
    return total_count

此代码尝试解决过度递归和潜在错误的问题：

最大递归深度处理：它引入了一个深度参数来跟踪递归深度，如果深度超过10，则会引发

RecursionError

。

错误处理：它尝试通过打印错误消息并返回 0 而不是传播错误来处理潜在的

RecursionError

异常。

与更简单的版本相比，该代码引入了额外的复杂点，并且设置固定的最大递归深度 10 可能不足以满足任意深度的嵌套。 那么，有没有一种替代方法可以不依赖深度递归地遍历嵌套列表，既可以处理深度递归，又可以降低复杂度呢？

Answer 1

为了避免深度递归带来的错误，你必须避免递归。

想想计算机的实际工作原理。递归创建隐式状态堆栈。当您返回时，您将返回到之前的状态，并从当前位置继续。

要失去递归，您必须保留显式堆栈。对于复杂的递归函数，您还需要弄清楚如何回到之前的同一点。但这是一个简单的递归函数。所以摆脱递归就这么简单：

def list_length (items):
    # Just works like a global variable. Now I don't need returns.
    total_length = 0
    # A stack of frames. Each frame contains an index and possible list.
    stack = [(0, items)]
    while 0 < len(stack):
        # Figure out the current state.
        i, these_items = stack.pop()
        # Do we need the equivalent of a recursive function?
        if isinstance(these_items, list):
            # Are we done with this list?
            if i < len(these_items):
                # When we come back to this "frame", we'll be on the next item.

                stack.append((i+1, these_items))
                # And our next loop iteration will be a "recursive" call.
                stack.append((0, these_items[i]))
        else:
            # Just an item. Because we already popped a "frame", we'll go back to the previous level of "recursion".
            total_length += 1
    # All done. Return the answer.
    return total_length

这就是如何在没有递归的情况下进行递归。这正是 Python 为您做的事情，只不过它是隐式地做的，而且它的堆栈帧中有更多内容。