Как передать значения при преобразовании рекурсивной функции в итеративную со стеком и циклом while ⇐ Python

[Anonymous]

РЕДАКТИРОВАТЬ: Мой первоначальный рекурсивный код был неполным, так как я не умножил на f(l, r) сумму двух рекурсивных ветвей.
Для функции f(l, r), которая вычисляет что-то из узлов (l, r) двоичного дерева высоты max_height, я хочу вычислить общее количество значение путем сложения значений левого и правого дочерних узлов, умножения суммы на значение родительского узла и передачи его по дереву.
У меня есть работающая рекурсивная реализация этого, но теперь я хочу устранить рекурсию с помощью цикла while и структур стека. Моя проблема в том, что я не знаю, как «передавать» значения во время цикла while. То есть я не знаю, как мне воспроизвести поведение, когда я умножаю текущее значение f(l, r) на сумму двух ветвей рекурсии.
Я включил два фрагмента кода: первый — текущая рекурсивная реализация, а второй — моя попытка более итеративного подхода. Последний код требует доработки, и я разместил TODO с комментариями, чтобы указать на некоторые из моих вопросов.
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).
Попытайтесь удалить рекурсию:< /p>
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


Подробнее здесь: https://stackoverflow.com/questions/784 ... tive-one-w