如何将递归转成迭代
标签: # iteration # recursion # LeetCode # Python # 迭代 # 递归 # 算法

要理解递归,先得理解递归
发现问题
函数的递归调用是码农在日常工作中不可或缺的利器,在某些问题上,函数递归可以提供更为简洁的代码实现和更为直观的阅读理解,比如说我们很熟悉的树形结构的遍历。
然而,当函数调用的层数过多的时候,就可能导致著名的 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
将嵌套列表扁平化
为了说明简单,这里使用与某刷题网站上同样的类定义来表示嵌套列表,即列表中的每个元素既可以是一个整数,也可以是一个列表,要求将其中所有的整数都存在列表的第一层并输出。比如说对于一个嵌套列表 [1,2,[3,4],[[5],6,[7]]]
,希望得到 [1,2,3,4,5,6,7]
。
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
2021/10/29 更新
昨晚写完本文之后,今早才发现原来网上已经有了很多文章介绍类似的技巧,其中示例问题、编程语言、具体实现有所不同,但思想是一致的,为了更全面的记录,我把这些文章都加进了参考链接里👇🏻。