вместо произвольной рекурсии, используя стек?

Question

Кажется очевидным, что рекурсия реализуется с использованием стеков. Но как вообще была реализована общая рекурсия с использованием стека? Например, если у нас есть пользовательская функция, которая рекурсивна, можем ли мы переписать код, используя только стек и итерацию?

Вот один пример (я давал неправильный пример в другом посте):

def recursiveCall(node): 
    if node==None: 
     return (0,True) 
    (left,lstatus) = recursiveCall(node.left) 
    (right,rstatus) = recursiveCall(node.right) 
    if lstatus==True and rstatus==True: 
     if abs(left-right)<=1: 
      return (max(left,right)+1,True) 
     else: 
      return (0,False) 
    else: 
     return (0,False) 

или проще один:

def recursiveInorder(node): 
    if node==None: 
     return 
    recursiveInorder(node.left) 
    print(node.val) 
    recursiveInorder(node.right) 

, как вы понимаете, это рекурсию с помощью стеки? Обратите внимание, что я не прошу об итерационном решении вышеупомянутых двух примеров. Я считаю, что должно быть. Но я полагаю, что эти итерационные решения не пытаются воспроизвести механизм рекурсии с использованием стека. Я хотел бы видеть, если это возможно, эти рекурсии могут быть полностью заменены специальным закодированным стековым механизмом (в основном создающим механизм неявной рекурсии, встроенный в компилятор или что-то явно).

Я думаю, нужно найти способ отслеживания и восстановления статуса программы, локальных переменных и т. Д.? thx.

---

класс узла определяется как:

class node: 
    def __init__(self,x): 
     self.val=x 
     self.left=None 
     self.right=None 

Answer 1

В принципе, при моделировании рекурсивный вызов, вам необходимо нажать на стек локальных переменных и в точке, где исполнение должно возобновить после возвращения.

Здесь я укажу соответствующие пункты выполнения с помощью пронумерованных комментариев. Думайте о них как goto этикетки.

def recursiveInorder(node): 
    #0 
    if node==None: 
     return 
    recursiveInorder(node.left) 
    #1 
    print(node.val) 
    recursiveInorder(node.right) 
    #2 
    return 

Теперь мы можем использовать if-elif заявление для имитации goto заявления:

def in_order(node): 
    stack = [(None, None)] #sentinel 
    goto = 0 
    while stack: 
     if goto == 0: 
      if node is None: 
       #return 
       (node, goto) = stack.pop() 
      else: 
       #push state and recurse left 
       stack.append((node, goto+1)) 
       (node, goto) = (node.left, 0) 
     elif goto == 1: 
      print(node.val) 
      #push state and recurse right 
      stack.append((node, goto+1)) 
      (node, goto) = (node.right, 0) 
     else: 
      #return 
      (node, goto) = stack.pop() 

В конце концов, (None, None) будет совал, но значения никогда не используются, поскольку цикл while заканчивается.

---

Приведенный выше код является результатом простого преобразования. Затем мы можем применить различные оптимизации для упрощения.

Последний else филиал не приносит полезной работы. Мы можем удалить его, если мы также удалим нажатие, которое приведет нас туда.

def in_order(node): 
    stack = [(None, None)] #sentinel 
    goto = 0 
    while stack: 
     if goto == 0: 
      if node is None: 
       #return 
       (node, goto) = stack.pop() 
      else: 
       #push state and recurse left 
       stack.append((node, goto+1)) 
       (node, goto) = (node.left, 0) 
     else: 
      print(node.val) 
      #recurse right 
      (node, goto) = (node.right, 0) 

Теперь значение goto что выталкивается из стека всегда 1. Нам нужно всего лишь нажать node в стек и назначить goto = 1 когда выскакивают из стека.

def in_order(node): 
    stack = [None] #sentinel 
    goto = 0 
    while stack: 
     if goto == 0: 
      if node is None: 
       #return 
       (node, goto) = (stack.pop(), 1) 
      else: 
       #push state and recurse left 
       stack.append(node) 
       (node, goto) = (node.left, 0) 
     else: 
      print(node.val) 
      #recurse right 
      (node, goto) = (node.right, 0) 

Если изменить внутреннюю if в while петлю ...

def in_order(node): 
    stack = [None] #sentinel 
    goto = 0 
    while stack: 
     if goto == 0: 
      while node is not None: 
       #push state and recurse left 
       stack.append(node) 
       node = node.left 
      #return 
      (node, goto) = (stack.pop(), 1) 
     else: 
      print(node.val) 
      #recurse right 
      (node, goto) = (node.right, 0) 

... мы видим, что после каждой ветви if заявления, мы хотим, чтобы перейти к другой ветви, пока в конце мы не выставим значение дозорного.Мы можем исключить goto и инструкцию if, если мы добавим проверку для пустого стека посередине. Если мы поместим чек перед попсом, нам больше не нужен дозорный стек.

def in_order(node): 
    stack = [] 
    while True: 
     while node is not None: 
      stack.append(node) 
      node = node.left 
     if stack: 
      node = stack.pop() 
      print(node.val) 
      node = node.right 
     else: 
      return 

Теперь код выглядит чистым и простым.