5

如何将递归转成迭代

 2 years ago
source link: https://old-panda.com/2021/10/28/how-to-convert-recursion-to-iteration/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

如何将递归转成迭代

Posted by OldPanda 2021-10-28 in Python
stone-stack-scaled.jpeg

要理解递归，先得理解递归

函数的递归调用是码农在日常工作中不可或缺的利器，在某些问题上，函数递归可以提供更为简洁的代码实现和更为直观的阅读理解，比如说我们很熟悉的树形结构的遍历。

然而，当函数调用的层数过多的时候，就可能导致著名的 Stack Overflow 错误，而栈空间一般是由编译器（ C/C++ 等）或者 Java 虚拟机（ Java 系语言）来管理，对程序员是不可见的，当然我们可以通过配置参数来调整程序的栈空间大小，但不免麻烦，并且递归层数一增加，栈很可能又要溢出。

尾递归是一个常用的优化方法，很多语言在执行的时候会识别这种优化，因为递归函数调用是一个函数的最后一步，所以在递归调用之前，就可以把当前函数调用从栈中弹出，再把新的函数调用压栈，这样就不会因为递归深度的增加吃掉栈空间了。

但尾递归并不是很容易就能实现的，用二叉树的中序遍历举例，它的递归版本非常简单直观，

# 树节点的定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        

def inorder_traversal(node):
    if node is None:
        return []
    left = inorder_traversal(node.left)
    right = inorder_traversal(node.right)
    return left + [node.val] + right

但试图将其转成尾递归则非常麻烦，以为它包含两个递归调用，并且两个递归调用的结果在最终要拼接在一起返回。这时如果还想避免栈溢出的问题，就需要将它转成迭代的形式，乍一听也是一个不太容易的工作，虽然某刷题网站给出了迭代形式的代码，但我个人认为这个答案写得并不易于理解，读完之后与其说是我在尝试理解迭代的过程，倒不如说是在死记硬背，我们需要一种更直接的方式将递归代码转成迭代代码。

函数递归本质上是函数调用入栈出栈的过程，并且在其中隐式地含有每一个函数调用的状态，函数通过查看这个状态来决定是否已满足停止条件，所以我们自然而然地想到用栈数据结构来模拟函数递归的过程。

同样地，以二叉树的中序遍历为例，每一层函数调用处理一个节点，同时还需要一个变量来记录当前节点的左子树是否已经遍历完毕，同时这个状态变量还担负起避免重复遍历同一条路径的作用，为简单起见，用整数 0 ， 1 ， 2 分别表示“第一次访问该节点”，“该节点的左子树已经遍历”，“该节点本身已经被遍历”，所以初始状态为，

stack = [[node, 0]]

然后用一个 while 循环来检查栈的长度，只要不为空，说明模拟的函数递归调用还没有结束，在每一次循环中，查看状态变量，如果

  • 为 0 ，说明第一次访问该节点，如果它的左子树不为空，将左子树节点压栈，并将状态置为 1 ，这是因为下一次访问到这个节点的时候，它的左子树节点必然已经全部出栈，这时就该遍历该节点本身了
  • 为 1 ，说明该节点的左子树遍历已经完成，将当前节点的值存到结果列表中，并将状态置为 2
  • 为 2 ，说明该节点已经被遍历，此时应该将该节点出栈，如果它的右子树不为空的话，将其右节点入栈

这样完整的二叉树中序遍历迭代版代码为，

def inorder_traversal(node):
    if not node:
        # 边缘情况检查
        return []

    output = []
    stack = [[node, 0]]

    while stack:
        node, status = stack[-1]
        if status == 0:
            stack[-1][1] = 1
            if node.left:
                stack.append([node.left, 0])
        elif status == 1:
            stack[-1][1] = 2
            output.append(node.val)
        else:
            stack.pop()
            if node.right:
                stack.append([node.right, 0])
    return output

这样看起来是不是更加简单易懂了呢？

更多的例子

二叉树的后续遍历

树的后续遍历的迭代版本一向以令人头大著称，配合上某刷题网站的题解，就更加扑朔迷离了，那么这个问题能不能套用上述转换“公式”呢？当然可以，但首先要确定不同状态的含义。

与中序遍历略有不同，在这里用数字 0 ， 1 ， 2 来分别表示“初次访问该节点”，“左子树已遍历完成”，“右子树已遍历完成”的状态。在每一次循环中，查看当栈中的节点状态

  • 为 0 ，初次访问该节点，将状态置为 1 ，如果该节点的左子树存在的话，将左子树入栈
  • 为 1 ，该节点的左子树遍历完成，将状态置为 2 ， 如果该节点的右子树存在的话，将右子树入栈
  • 为 2 ，该节点的右子树遍历完成，将当前节点的值存入结果列表中，然后该节点出栈

逻辑顺序理清了，就不难写出如下代码，

def postorder_traversal(node):
    if not node:
        # 边缘情况检查
        return []

    output = []
    stack = [[node, 0]]

    while stack:
        node, status = stack[-1]
        if status == 0:
            stack[-1][1] = 1
            if node.left:
                stack.append([node.left, 0])
        elif status == 1:
            stack[-1][1] = 2
            if node.right:
                stack.append([node.right, 0])
        else:
            output.append(node.val)
            stack.pop()
    return output

将嵌套列表扁平化

为了说明简单，这里使用与某刷题网站上同样的类定义来表示嵌套列表，即列表中的每个元素即可以是一个整数，也可以是一个列表，要求将其扁平化并输出。

class NestedInteger:
    def isInteger(self) -> bool:
        """
        @return True if this NestedInteger holds a single integer, rather than a nested list.
        """

    def getInteger(self) -> int:
        """
        @return the single integer that this NestedInteger holds, if it holds a single integer
        Return None if this NestedInteger holds a nested list
        """

    def getList(self) -> [NestedInteger]:
        """
        @return the nested list that this NestedInteger holds, if it holds a nested list
        Return None if this NestedInteger holds a single integer
        """

它的递归版本也很简单，遇到整数就直接输出，遇到列表就递归调用自己并返回结果，

def flatten_list(nested_list: [NestedInteger]):
    result = []
    def flatten(nested_list):
        for item in nested_list:
            if item.isInteger():
                result.append(item.getInteger())
            else:
                result.extend(flatten(item.getList()))
        return result
    return flatten(result)

现在，让我们尝试套用上述“公式”将其转换为迭代版本。首先，要明确状态变量的含义，因为每一次的递归调用是作用在一个列表上的，所以当用栈模拟函数调用时，状态变量可以规定为当前正在处理数组的下标，这样初始状态则为

stack = [[nested_list, 0]]

在每一次循环中，若当前元素为整数，将该整数存到结果数组中，并将状态变量加一，代表着当前元素已经处理完毕；如果当前元素为列表，则将该列表与其初始状态（ 0 ）入栈，同时将状态加一；如果状态超出了列表的范围，则代表该列表已经被处理完毕，可以出栈。因此，最终的代码为

def flatten_list(nested_list: [NestedInteger]):
    result = []
    stack = [[nested_list, 0]]
    while stack:
        l, status = stack[-1]
        if status >= len(l):
            stack.pop()
            continue
        if l[status].isInteger():
            result.append(l[status].getInteger())
            stack[-1][1] += 1
        else:
            stack[-1][1] += 1
            stack.append([l[status].getList(), 0])
    return result

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK