Перевод рекурсии с глобальными переменными в итерацию с использованием стека

Question

Как бы вы перевели рекурсивную функцию, которая использует глобальные переменные, в итерационную?

Одним из примеров этого является использование поиска в глубину, где я хочу отслеживать путь:

path = []

function dfs(node)
    node.visited = true
    path.append(node)

    if node == goal
        print path
        stop;

    for child in node.children
        if !child.visited
            dfs(child)

    path.pop()

Как бы я это сделал, используя итерацию и стек?

Answer 1

Если бы вы могли расширить класс Node, он будет выглядеть следующим образом.

function iterative_dfs(start_node)
    start_node.next = null
    start_node.visited = true

    stack = []
    stack.push(start_node)

    while !stack.empty?
        node = stack.pop

        if node == goal
            path = []
            while node
                path.push(node)
                node = node.next
            path.reverse
            print path
            stop;

        for child in node.children
            if !child.visited
                child.next = node
                child.visited = true
                stack.push(child)

Кроме того, в вашем коде есть ошибка.Вы должны открыть узел, если не можете найти цель.

function dfs(node)
    node.visited = true
    path.append(node)

    if node == goal
        print path
        stop;

    for child in node.children
        if !child.visited
            dfs(child)

    path.pop    # You need this