Как определить последнее место в стеке в рекурсии - PullRequest
Новая
       37

Как определить последнее место в стеке в рекурсии

0 голосов
/ 06 декабря 2018

Я реализую общеизвестный поиск в глубину с помощью рекурсии.Интересно, может ли быть способ узнать код в последнем пространстве стека?Почему мне нужно, я не хочу ставить символ -> в конце вывода.Если это возможно, просто '\n' на последнем шаге. 

def DFS(self, vertex=None, visited=None):
    if vertex is None:
        vertex = self.root
    if visited is None:
        visited = []
        print(f"{vertex} -> ", end='')

    visited.append(vertex)
    for neighbor in self.getNeighbors(vertex):
        if neighbor not in visited:
            visited.append(neighbor)
            print(f"{neighbor} -> ", end='')
            self.DFS(neighbor, visited)

Например, он дает 1 -> 2 -> 4 -> 5 ->

Есть ли что-то сделать в том же методе?Более того, я мог бы написать вспомогательную функцию, удаляющую последний -> символ.

@ Edit: то, что я сделал в соответствии с комментарием @ Carcigenicate, следует 

return visited # last line in DFS method
-- in main --
dfs = graph.DFS()
path = " -> ".join(str(vertex) for vertex in dfs)
print(path)

1 Ответ

0 голосов
/ 07 декабря 2018

Вместо того, чтобы пытаться создать особый случай последней вершины, особый случай - первой.То есть не пытайтесь выяснить, когда не следует добавлять "->", просто не делайте этого для первой вершины: 

def DFS(self, vertex=None, visited=None):
    if vertex is None:
        vertex = self.root
    else:
        # Not the first vertex, so need to add the separator.
        print(f" ->", end='')

    if visited is None:
        visited = []

    print(f"{vertex}", end='')

    visited.append(vertex)
    for neighbor in self.getNeighbors(vertex):
        if neighbor not in visited:
            # no need to append here, because it will be done in the recursive call.
            # and the vertex will be printed in the recursive call, too.
            # visited.append(neighbor)
            # print(f"{neighbor} -> ", end='')
            self.DFS(neighbor, visited)

Это предполагает, что ваш начальный вызов всегда будет DFS(root, None, visited).Что я считаю разумным предположением.

Если подумать, возможно, лучше использовать параметр visited в качестве условия: 

    if vertex is None:
        vertex = self.root

    if visited is None:
        visited = []
    else:
        # Not the first vertex, so need to add the separator.
        print(f" ->", end='')

    print(f"{vertex}", end='')

Суть в том, что легчеспециальный случай первый элемент, чем последний.

...