原文: Tricks of the trade: Recursion to Iteration, Part 3: Recursive Data Structures

这是将递归算法转换为迭代算法系列的第三篇。如果下面的任何内容看起来令人困惑，你可能想先阅读前面两章的内容

这是我没有计划的一篇附加文章。之所以写它，是因为在上一篇文章的评论中，有读者要求我展示一个不那么数学化的例子，并建议使用树遍历。所以这就是这篇文章的主题。我们把一颗二叉树扁平化成一个列表，先是递归，然后是迭代

挑战

首先，我们定义一棵二叉树，要么是空的，要么是由一个节点给出的，有三个部分。(1) 一个值 (2) 一个左子树 (3) 一个右子树，其中两个子树本身就是二叉树。在Haskell中，我们可以这样定义。

1
data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a)

在Python中，我们将在本文余下的内容中使用Python，我们说None代表一颗空树，如下Class表示一个节点

1
2
3
4
5
6
7
8
9
import collections
Node = collections.namedtuple('Node', 'val left right')

tree0 = None
tree1 = Node(5, None, None)
tree2 = Node(7, tree1, None)
tree3 = Node(7, tree1, Node(9, None, None))
tree4 = Node(2, None, tree3)
tree5 = Node(2, Node(1, None, None), tree3)

现在让我们定义一个函数，用前序遍历 的方式来扁平化一棵树。递归定义非常简单，数据类型只有两种情况需要考虑

1
2
3
4
def flatten(bst):
  if bst is None:
    return []
  return flatten(bst.left) + [bst.val] + flatten(bst.right)

通过一些测试来检查它是否符合我们的预期:

1
2
3
4
5
6
7
8
9
10
def check_flattener(f):
  assert f(tree0) == []
  assert f(tree1) == [5]
  assert f(tree2) == [5,7]
  assert f(tree3) == [5,7,9]
  assert f(tree4) == [2,5,7,9]
  assert f(tree5) == [1,2,5,7,9]
  print("ok")

check_flattener(flatten)

我们今天的挑战是将flatten转换成迭代版本。除了一个新的技巧 – partial evaluation之外，这个转换很直接，所以我将快速略过步骤

来吧～～～

消除第一个递归调用

首先，我们把基础工作和增量工作分开。

1
2
3
4
5
6
7
def step(bst):
  return flatten(bst.left) + [bst.val] + flatten(bst.right)

def flatten(bst):
  if bst is None:
    return []
  return step(bst)

让我们把增量的工作分解成小块，看看是怎么回事儿。

1
2
3
4
5
6
7
8
9
10
11
def step(bst):
  left = flatten(bst.left)
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return left

def flatten(bst):
  if bst is None:
    return []
  return step(bst)

让我们尝试摆脱第一个递归调用，假设有人通过一个秘密参数left传给我们它的结果

1
2
3
4
5
6
7
8
9
10
11
12
def step(bst, left=None):
  if left is None:
    left = flatten(bst.left)
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return left

def flatten(bst):
  if bst is None:
    return []
  return step(bst)

现在我们将使step返回值与它的输入参数平行

1
2
3
4
5
6
7
8
9
10
11
12
def step(bst, left=None):
  if left is None:
    left = flatten(bst.left)
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return bst, left

def flatten(bst):
  if bst is None:
    return []
  return step(bst)[-1]

在第一次递归调用中，应用于bst的变换是.left,所以我们要在返回的值中对bst应用相反的变换。而下降到节点的左子树的相反变换是什么呢？是上升到节点的父节点。所以我们想要这样的东西

1
2
3
4
5
6
7
8
9
# 注意，以下代码不工作

def step(bst, left=None):
  if left is None:
    left = flatten(bst.left)
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return get_parent(bst) , left  # <-- 需要get_parent

但是我们被卡住了，我们不能定义get_parent, 因为我们的树形数据结构不跟踪父母(子节点没有指针指向父节点)，只跟踪子女

新计划: 也许我们可以假设有人把节点的父节点传给了我们，然后从那里开始？

但是这个计划同样碰到了铜墙铁壁。如果我们增加一个新的参数来接收父。我们必须为了并行性增加一个新的返回值来发转转换后的父，也就是父的父。但是我们无法计算出父的父，因为和之前一样，我们没办法实现get_parent.

所以我们就像数学家一样，当它们的假设撞上了一堵墙：我们加强我们的假设！现在我们假设有人把所有的父母都传给了我们，直到根。而这个假设给了我们所需要的东西。

1
2
3
4
5
6
7
def step(bst,parents,left=None):
  if left is None:
    left = flatten(bst.left)
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return parents[-1], parents[:-1], left

请注意，我们使用Python栈来表示父类，因此bst的直接父由最终元素parents[-1]给出。

作为一种简化，我们可以去掉bst参数，把它看作是推到栈上的最后一个父参数

1
2
3
4
5
6
7
8
def step(parents, left=None):
  bst = parents.pop()   # <-- bst = parents栈的顶部
  if left is None:
    left = flatten(bst.left)
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return parents, left

现在step需要parents栈作为参数，基础函数必须提供它

1
2
3
4
5
def flatten(bst):
  if bst is None:
    return []
  parents = [bst]
  return step(parents)[-1]

但我们仍然没有消除第一个递归调用。要做到这一点，我们需要为step函数的left参数传递一个值。这将导致递归调用被跳过。

但我们只知道在一种情况下，即基本情况下，当bst是None，那么left一定是[]。为了从树的根部到达这种情况，即bst绝对不是None, 我们必须迭代复制对bst.left的正常递归调用，直到我们碰到最左边的叶子节点。然后，为了计算结果，我们必须反转行程，迭代step函数，直到回到树的根部，那里的parents栈必须是空的

1
2
3
4
5
6
7
8
9
10
11
def flatten(bst):
  left = []
  parents = []
  while bst is not None:
    parents.append(bst)
    bst = bst.left
  
  while parents:
    parents, left = step(parents, left)
  
  return left

就这样，其中一个递归调用已经转变成了迭代。我们离终点线已经有一半的距离了！

消除第二个递归调用

但是我们依旧要取消最后的递归调用，即扁平化，现在被封存的步骤中。让我们仔细看看那个函数，在我们使其left参数成为必须之后，它现在总是带着一个值被调用。

1
2
3
4
5
6
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  right = flatten(bst.right)
  left.extend(right)
  return parents, left

为了摆脱对flatten的递归调用，我们将使用一个新的技巧：partial evaluation. 基本上，在重命名所有变量防止冲突之后，我们将使用flatten函数体替换flatten调用。因此，让我们复制Flatten, 并给它所有变量添加后缀1

1
2
3
4
5
6
7
8
9
10
def flatten1(bst1):
  left1 = []
  parents1 = []
  while bst1 is not None:
    parents1.append(bst1)
    bst1 = bst1.left
  while parents1:
    parents1, left1 = step(parents1, left1)
   
  return left1

然后让我们明确它的参数和返回值

1
2
3
4
5
6
7
8
9
10
11
12
(bst1, ) = ARGUMENTS

left1 = []
parents1 = []
while bst1 is not None:
  parents1.append(bst1)
  bst1 = bst1.left

while parents1:
  parents1, left1 = step(parents1, left1)
  
RETURNS = (left1,)

然后我们再把这个扩展降到step:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  
  # --- begin partia evaluation
  (bst1, ) = (bst.right, )
  
  left1 = []
  parents1 = []
  while bst1 is not None:
    parents1.append(bst1)
    bst1 = bst1.left
  while parents1:
    parents1,left1 = step(parents1,left1)
  (right,) = (left1,)
  # end partial evaluation
  left.extend(right)
  return parents, left

现在我们来简化代码

首先是: left1. 我们现在可以看到，这个变量累积的值，最后会被追加到left上(通过返回变量right)。但我们也可以直接将这些值追加到left上，在边界内消除left1，而不调用left.extension(right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  # -- begin partial evaluation
  bst1 = bst.right
  # left1 = []  # <-- 删除并使用left替代
  parents1 = []
  while bst1 is not None:
    parents1.append(bst1)
    bst1 = bst1.left
  while parents1:
    parents1, left = step(parents1, left)
  
  # right = left  <--- 删除
  # -- end partial evaluation
  # left.extend(right) <-- 删除
  return parents, left

在接下来的融合中，我们需要调用我们的基础函数来获得必要的外部作用域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  #-- begian partial evaluation
  bst1 = bst.right
  parents1 = []
  while bst1 is not None:
    parents1.append(bst1)
    bst1 = bst1.left
  while parents1:
    parents1,left = step(parents1, left)
  #-- end partial evaluation
  return parents, left

def flatten(bst):
  left = []
  parents = []
  while bst is not None:
    parents.append(bst)
    bst = bst.left
  while parents:
    parents, left = step(parents, left)
    
  return left

当flatten调用step, 部分执行区域内的代码执行时，它会建立一个节点parents1栈，然后反复调用step，从栈中弹出值并处理。当它完成后，控制返回到step proper, 然后它带着值(parents, left) 返回给它的调用者flatten。但是看看flatten对parents的处理：它迭代的调用step, 从栈中弹出值，并以完全相同的方式处理它们。

所以我们可以取消step中的while循环 – 以及递归调用!!! 不返回parents, 而是返回parents + parents1, 这将使flatten中的while循环做完全相同的工作

1
2
3
4
5
6
7
8
9
10
11
12
13
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  #-- begin partial evaluation
  bst1 = bst.right
  parents1 = []
  while bst1 is not None:
    parents1.append(bst1)
    bst1 = bst1.left
  # while parents1:  <-- 删除
  #    parents1,left = step(parents1, left) #
  #-- end partial evaluation
  return parents + parents1 ,left # parents -> parents + parents1

然后我们就可以把我们本来附加在它上面的值，直接附加到parents上，就可以完全删除parents1.

1
2
3
4
5
6
7
8
9
10
11
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  #-- begin partial evaluation
  bst1 = bst.right
  #parents1 = []  <-- 删除
  while bst1 is not None:
    parents.append(bst1)
    bst1 = bst1.left
  #-- end partial evaluation
  return parents, left # parents + parents1 -> parents

现在，一旦我们去掉了我们的partial-evaluation脚手架，我们的step函数就又显得简单了

1
2
3
4
5
6
7
8
def step(parents, left):
  bst = parents.pop()
  left.append(bst.val)
  bst1 = bst.right
  while bst1 is not None:
    parents.append(bst1)
    bst1 = bst1.left
  return parents, left

对于我们旅程的最后一站 – 简化，让我们将step逻辑内嵌到基础函数中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def flatten(bst):
  left = []
  parents = []
  while bst is not None:
    parents.append(bst)
    bst = bst.left
  while parents:
    parents,left = parents,left
    bst = parents.pop()
    left.append(bst.val)
    bst1 = bst.right
    while bst1 is not None:
      parents.append(bst1)
      bst1 = bst1.left
    parents,left = parents,left
  return left

让我们消除琐碎参数绑定和返回值赋值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def flatten(bst):
  left = []
  parents = []
  while bst is not None:
    parents.append(bst)
    bst = bst.left
  while parents:
    # parents, left = parents, left
    bst = parents.pop()
    left.append(bst.val)
    bst1 = bst.right
    while bst1 is not None:
      parents.append(bst1)
      bst1 = bst1.left
    # parents, left = parents, left 
  return left

最后，将重复的while循环变成一个局部函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def flatten(bst):
  left = []
  parents = []
  def descend_left(bst):
    while bst is not None:
      parents.append(bst)
      bst = bst.left
  
  descend_left(bst)
  while parents:
    bst = parents.pop()
    left.append(bst.val)
    descend_left(bst.right)
  return left

完成了! 我们现在有了一个紧凑、高效、迭代的函数。另外，该代码接近惯用法。