python - 将递归转换为迭代python

Question

def nested_depth(L):
"""

>>> nested_depth([1, 2, 3])
1
>>> nested_depth([1, [2, 3], 4])
2
"""

    return (1 + max([nested_depth(x) for x in L])
            if isinstance(L, list) else 0)

如何将此递归代码转换为迭代代码？即我们必须使用循环并且我们不允许调用函数本身。

谢谢

Answer 1

有一种“通用”方法可以将递归转换为迭代。您必须引入并维护自己的堆栈，以维护由递归执行的函数帧堆栈为您维护的状态。例如：

def max_nested_depth(items):
    assert type(items) == list
    max_depth = depth = 1

    # Use a stack to maintain the position in each layer of lists.

    stack = [(0, items)]

    while stack: # Continue until the stack is empty.

        # Iterate each layer until the index exceeds the end of the list.

        while stack[-1][0] < len(stack[-1][1]):

            pos, items = stack[-1]
            stack[-1] = (pos + 1, items)

            if type(items[pos]) == list:

                # Here's the recursion step.

                stack.append((0, items[pos]))
                depth += 1
                max_depth = max(max_depth, depth)

        stack.pop()
        depth -= 1

    return max_depth

Answer 2

>>> def maxDepth(L):
...   answer = 1
...   while L:
...     if not any(isinstance(i, list) for i in L):
...       return answer
...     answer += 1
...     L = list(itertools.chain.from_iterable([i for i in L if isinstance(i, list)]))
... 
>>> L = [1,2,3]
>>> maxDepth(L)
1
>>> L = [1,[2,3],4]
>>> maxDepth(L)
2

Answer 3

与@inspectorG4dget 相同的想法

def max_depth(L):
    ans = 0
    while L:
        L = [j for i in L for j in (i if isinstance(i, list) else [])]
        ans += 1
    return ans