Как вообще перевести рекурсивную программу в итеративную? - PullRequest
Новая
       35

Как вообще перевести рекурсивную программу в итеративную?

1 голос
/ 09 января 2020

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

Вот оригинальная рекурсивная функция обхода BST:

Python 3 

def traverse_rec(node):  # traversal of sub-tree at node.
    # pre-order work here:
    # print(node.val, end=' ')
    if node.lft:
        traverse_rec(node.lft)

    # in-order work here:
    print(node.val, end=' ')

    # post-order work here:
    # print(node.val, end=' ')
    if node.rt:
        traverse(node.rt),

Я нашел несколько итерационных версий рекурсивных функций (до, в, после -порядок BST traverse) например здесь , но я ищу итеративную реализацию, которая следует , что компьютер делает со своим стеком вызовов , чтобы я мог так же легко конвертировать пост-заказ Обход BST и, в более общем случае, преобразование рекурсивного кода в итеративный. Таким образом, «кадр» должен помещаться в стек фреймов каждый раз, когда вызывается функция, в которой записывается, где продолжить выполнение при возврате функции, а также любые переменные, необходимые вызывающей функции, которые могут быть изменены вызываемой функцией. Кадры извлекаются из стека кадров при возврате функции.

1 Ответ

0 голосов
/ 09 января 2020

Вот мой рекурсивный итеративный перевод с использованием frame_stack: 

def traverse_iter(node):
    # Iterative bst traversal. A (node, state) tuple is pushed onto frame_stack where a recursive call would occur.
    # state defines where to pick up the processing on return (on pop).
    # state: 0: Did not just return into this frame.
    #        1: Just returned from left child.
    #        2: Just returned from right child.
    # Only states 1 and 2 get pushed onto the frame_stack.
    # Generally, state would include any variables that are needed on return that get changed on the frame change
    # in addition to the program counter (pc).
    # Here, each node has all the data (val) needed, and state 1 or 2 acts as a pc to determine where to pick up
    # on return.
    frame_stack = []
    state = 0  # Didn't just return from a child(function call).
    while True:
        if node is None:    
            if frame_stack:  # Returning up recursion tree:
                node, state = frame_stack.pop()
            else:            # or completed traversal.
                break

        if state == 0:
            # Execute pre-order work here.
            #print(node.val, end=' ')
            if node.lft:  # Emmulate recursive call into left child.
                frame_stack.append((node, 1))
                node = node.lft
                continue

        if state == 0 or state == 1:
            # Execute in-order work here
            print(node.val, end=' ')

            if node.rt:
                frame_stack.append((node, 2))
                node = node.rt
                state = 0       # State to descend into child.
                continue

        # Returning from a right child or there was none:
        # Execute post-order work here.
        # print(node.val, end=' ')
        node = None     # finished with this node (and all below it).

Как только я «понял», я обнаружил, что довольно просто разработать и понять вышеизложенное, и кажется, что шаблон, который я использовал, обычно расширяемый для любого рекурсивного итеративного перевода, поскольку он основан на том, что делает компьютер. Я в основном перевожу рекурсивный вызов функции в обновление переменных, которые меняются в новую функцию (узел на дочерний узел здесь), и pu sh их исходные значения в стек фрейма (узел здесь) вместе с p c (укажите здесь); минимальная логика поддержки c была добавлена ​​по мере необходимости.

Мне интересно, может ли кто-нибудь привести пример, когда полезная нагрузка кадра требует больше, чем (узел, состояние), чтобы получить из функции return, где мы остановились, или упростить мой обход BST (сохраняя при этом предварительно, in- и post-order general).

...