Почему переменная пути не может быть возвращена?

Question

Я использую DFS для получения всех маршрутов между двумя узлами.

Мой код Python выглядит следующим образом:

graph = {0: [1, 2, 3], 
         1: [3], 
         2: [0, 1], 
         3: []}
def DFS(start, stop, path=[], visited=[]):
    global count
    global result

    # add the visited node to path
    path.append(start)
    # mark this node visited to avoid infinite loop
    visited.append(start)

    # found
    if start == stop:
        print(path)

    else:
        # if not found
        values = graph.get(start)
        for next_ in values:
            # not visited node
            if not next_ in visited:
                DFS(next_, stop, path, visited)

    # remove the node from path and unmarked it 
    path.remove(start)
    visited.remove(start)

проблема в том, что если я print path в if start == stop, все 3 маршрута могут быть напечатаны правильно.

>>> DFS(2, 3)
[2, 0, 1, 3]
[2, 0, 3]
[2, 1, 3]

Но если я перейду на return path в if start == stop, он ничего не вернет.

def DFS(start, stop, path=[], visited=[]):
    global count
    global result

    # add the visited node to path
    path.append(start)
    # mark this node visited to avoid infinite loop
    visited.append(start)

    # found
    if start == stop:
        return path

    else:
        # if not found
        values = graph.get(start)
        for next_ in values:
            # not visited node
            if not next_ in visited:
                DFS(next_, stop, path, visited)

    # remove the node from path and unmarked it 
    path.remove(start)
    visited.remove(start)


>>> result = DFS(2, 3)
>>> result

Answer 1

Но если я перейду на путь возврата, если start == stop, он ничего не вернет.

Right;потому что вы достигли этого уровня рекурсии из предыдущего, который рекурсивно вызвал DFS(next_, stop, path, visited) ... и проигнорировал результат.

Это то же самое, как если бы вы вызывали функции нормально:

def inner():
    return "hello"

def outer():
    inner() # oops, it is not returned.

print(outer()) # None

Как правило, вы хотите return результаты ваших рекурсивных вызовов;но ваш случай немного особенный, потому что вам нужно накапливать результаты нескольких рекурсивных вызовов (for next_ in values:). Вы можете создать список и вернуть его, но это немного сложно:

if start == stop:
    result = [path] # for uniformity, we need a list of paths in this case too.
    # Also, we can't `return` here, because we'll miss the cleanup at the end.
else:
    result = []
    values = graph.get(start)
    for next_ in values:
        # BTW, Python treats `not in` as a single operator that does
        # what we want here. It's preferred because it's easier to read.
        if next_ not in visited:
            # add results from the recursive call to our result.
            result.extend(DFS(next_, stop, path, visited))
            # it is `.extend` and not `.append` here because otherwise we will
            # build a tree of nested lists - do you understand why?
# Either way, we want to do our cleanup, and return the collected result.
path.remove(start)
visited.remove(start)
return result # important!

Сложно, верно?

Поэтому мое предпочтительное решение для этих ситуаций - написать рекурсивный генератор и сбор результатов за пределами рекурсии:

# Inside the function, we do:
if start == stop:
    yield path
else:
    values = graph.get(start)
    for next_ in values:
        if next_ not in visited:
            yield from DFS(next_, stop, path, visited))
path.remove(start)
visited.remove(start)

# Then when we call the function, collect the results:
paths = list(DFS(2, 3))
# Or iterate over them directly:
for path in DFS(2, 3):
    print("For example, you could take this route:", path)

(Кроме того, полученный вами комментарий был хорошим советом. Рекурсию намного проще понять, если вы не пытаетесь мутироватьаргументы и очистите потом. Вместо этого всегда передавайте эти аргументы, а когда вы делаете рекурсивный вызов, передайте измененную версию. Когда рекурсия возвращается, очистка происходит автоматически, потому что вы просто возвращаетесь к использованию старого объекта в старом стеке. кадр.

Answer 2

Проблема с вашим кодом заключается в том, что

result=DFS(3,2)

вернет действительный результат только в том случае, если start = stop, что не так, как 3! = 2. Чтобы получить желаемый результат, вы должны изменить строку

DFS(next_,stop,path,visited) 

на

return DFS(next_,stop,path,visited)

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