递归转迭代（栈+While循环）时的数值传递问题

编辑说明：我最初的递归代码存在疏漏，未将两个递归分支的和与f(l, r)相乘。

给定函数f(l, r)，用于计算高度为max_height的二叉树中节点(l, r)的相关值，需要通过将左右子节点的值相加后与父节点的值相乘，沿树传递并计算总数值。

已有可正常运行的递归实现，但希望用while循环和栈结构消除递归。目前的问题是不知道如何在while循环中“传递”数值，即不知道如何复现将当前值f(l, r)与两个递归分支的和相乘的行为。

递归实现代码 #

def recursive_travel(l, r, cur_height, max_height):
    if cur_height == max_height - 1:
       return f(l, r) * (f(l + 1, r) + f(l, r + 1))
    return f(l, r)* (recursive_travel(l + 1, r, cur_height + 1, max_height) + recursive_travel(l, r + 1, cur_height + 1, max_height))

初始调用方式：recursive_travel(0, 0, 0, max_height)

待完善的迭代实现尝试 #

def iterative_travel(max_height):
  call_stack = [(0, 0, 0)] # cur_height, l, r in that order
  handled_stack = [] # TODO: Maybe I need to have something like this, or maybe I need a double array to store computed values?

  # Precompute the value of r_c directly to an n x n table for fast access
  pre_f = [[f(l, r) for l in range(0, max_height + 1)] for r in range(0, max_height + 1)]

  while call_stack:
    cur_height, l, r = stack.pop()
    if max_height - 1 == cur_height: 
      # TODO: Not sure how to pass on the computed values

      # TODO: Where I should put this value? In some table? In some stack?
      value = pre_f[l, r] * (pre_f[l + 1, r] + pre_f[l, r + 1])

      # TODO: Should I mark somewhere that the node (l, r) has been handled?
    elif handled_stack:
      # TODO: Not sure how to handle the computed values
      pass
    else:
      # TODO: Do I do something to the current l and r here?
      stack.append((current_depth + 1, l + 1, r))
      stack.append((current_depth + 1, l, r + 1))
  return 0 # TODO: Return the correct value

要将递归转为迭代，核心是用栈模拟递归调用的上下文，同时需要记录每个节点的处理状态（是否已经处理过子节点），以及存储子节点的计算结果。这里采用标记法即可实现：

具体实现思路 #

1. 栈元素设计：每个栈元素为(is_processed, cur_height, l, r)，is_processed为布尔值——True表示该节点的子节点已处理完毕，现在需要计算当前节点的值；False表示该节点尚未处理子节点，需要先触发子节点的处理。
2. 结果缓存：用字典memo存储已计算的节点值，对应递归中函数的返回值传递。
3. 处理流程：
   • 弹出栈顶元素，若未处理过，则先将当前节点标记为已处理后重新压入栈，再依次压入右、左子节点（栈是后进先出，这样左子节点会先被处理）。
   • 若已处理过，则根据当前高度计算节点值：
     • 叶子节点直接计算并存入memo；
     • 非叶子节点从memo取出左右子节点的结果，求和后与当前节点的f(l,r)相乘，存入memo。

完整迭代代码 #

def iterative_travel(max_height):
    # 预计算所有f(l,r)的值，修正原代码的索引错误，扩展范围避免越界
    pre_f = [[f(l, r) for r in range(max_height + 2)] for l in range(max_height + 2)]
    # 栈元素：(是否已处理, cur_height, l, r)
    stack = [(False, 0, 0, 0)]
    # 存储已计算的节点值
    memo = {}

    while stack:
        is_processed, cur_height, l, r = stack.pop()
        if not is_processed:
            # 标记当前节点为待处理，压回栈
            stack.append((True, cur_height, l, r))
            # 先压右子节点，再压左子节点，保证左子节点优先处理
            stack.append((False, cur_height + 1, l, r + 1))
            stack.append((False, cur_height + 1, l + 1, r))
        else:
            if cur_height == max_height - 1:
                # 叶子节点计算逻辑
                val = pre_f[l][r] * (pre_f[l+1][r] + pre_f[l][r+1])
                memo[(cur_height, l, r)] = val
            else:
                # 非叶子节点，利用子节点结果计算
                left_val = memo[(cur_height + 1, l + 1, r)]
                right_val = memo[(cur_height + 1, l, r + 1)]
                val = pre_f[l][r] * (left_val + right_val)
                memo[(cur_height, l, r)] = val
    # 返回根节点的最终计算结果
    return memo[(0, 0, 0)]

关键修正与说明 #

• 修正了原迭代代码中pre_f的索引错误：Python二维列表需用pre_f[l][r]访问，同时扩展预计算范围到max_height+2，避免叶子节点访问l+1、r+1时出现索引越界。
• 通过is_processed标记完美模拟递归的“先递后归”流程，先处理所有子节点，再回溯计算父节点的值。
• 用memo字典缓存计算结果，避免重复计算，对应递归中函数返回值的传递逻辑。

内容的提问来源于stack exchange，提问作者Epsilon Away