将递归函数转换为带有堆栈和 while 循环的迭代函数时如何传递值

Question

给定一个函数

f

从高度为

(l, r)

的二叉树的节点

max_height

计算某些内容，我想计算当我们将叶子加在一起并将总和与父节点相乘并将其传递时的总值树。

我有一个有效的递归实现，但现在我想用 while 循环和堆栈结构消除递归。我的问题是我不知道如何在 while 循环期间“传递”值。也就是说，当我将当前值

f(l, r)

与两个递归分支的总和相乘时，我不知道应该如何复制该行为。

我包含了两个代码片段：第一个是当前的递归实现，第二个是我对更加基于迭代的方法的尝试。后面的代码需要更多的工作，我已经注释了 TODO 来指出我的一些问题。

def recursive_travel(l, r, cur_height, max_height):
    if cur_height == max_height:
       return f(l, r) * (f(l+1, r) + f(l, r+1))
    return recursive_travel(l+1, r, cur_height+1, max_height) + recursive_travel(l, r+1, cur_height+1, 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

Answer 1

尝试：

def recursive_travel(l, r, cur_height, max_height):
    def f(l,r):
        return l+r
    if cur_height == max_height:
       return f(l, r) * (f(l+1, r) + f(l, r+1))
    return recursive_travel(l+1, r, cur_height+1, max_height) + recursive_travel(l, r+1, cur_height+1, max_height)
    
def stack_travel(l, r, min_height, max_height):
    # Define the function f
    def f(l, r):
        return l + r

    # Stack to hold states to process
    stack = [(l, r, min_height)]
    results = {}  # Dictionary to store the results of subproblems

    # Process until the stack is empty
    while stack:
        cur_l, cur_r, cur_height = stack.pop()

        # Calculate base case directly
        if cur_height == max_height:
            if (cur_l, cur_r, cur_height) not in results:
                results[(cur_l, cur_r, cur_height)] = f(cur_l, cur_r) * (f(cur_l + 1, cur_r) + f(cur_l, cur_r + 1))
        else:
            # Check if children results are ready
            left_key = (cur_l + 1, cur_r, cur_height + 1)
            right_key = (cur_l, cur_r + 1, cur_height + 1)

            # Calculate if children are already processed
            if left_key in results and right_key in results:
                results[(cur_l, cur_r, cur_height)] = results[left_key] + results[right_key]
            else:
                # Re-add current node to process later
                stack.append((cur_l, cur_r, cur_height))
                # Ensure children are in the stack to be processed
                if left_key not in results:
                    stack.append(left_key)
                if right_key not in results:
                    stack.append(right_key)

    # Return the result for the initial call
    return results[(l, r, min_height)]

# Test the function
print(recursive_travel(1, 2, 3, 4))
print(stack_travel(1, 2, 3, 4))
print(recursive_travel(5, 6, 7, 8))
print(stack_travel(5, 6, 7, 8))

输出：

80
80
624
624

表明堆栈版本按预期工作。