Python:为什么这个递归不改变输入列表？

Question

这是一个理解Python列表突变的问题。我解决了这个深度优先的搜索问题，得到了正确的结果。然后，我得到了一些反馈，在我看来，这不应该有效，但它是有效的。

基本上，如果我使用path而不是current_path (通过在注释行和非注释行对中切换行)，结果是相同的。我在试着弄明白为什么会这样。我理解列表路径中的列表(意思是路径)不会发生变异。但是，当我为路径的第0次索引分配一个不同的列表时，列表路径应该发生变异。但是，它运作得很好。

下面是代码，我把docstring留给了进一步的澄清。最后，为了更好地理解列表突变，我贴上了我玩过的代码，但这并没有帮助我。有人能解释一下吗？

# Problem 3b: Implement get_best_path
def get_best_path(digraph, start, end, path, max_dist_outdoors, best_dist,
                  best_path):
    """
    Finds the shortest path between buildings subject to constraints.
        digraph: Digraph instance
            The graph on which to carry out the search
        start: string, Building number at which to start
        end: string, Building number at which to end
        path: list composed of [[list of strings], int, int]
            Represents the current path of nodes being traversed. Contains
            a list of node names, total distance traveled, and total
            distance outdoors.
        max_dist_outdoors: int
            Maximum distance spent outdoors on a path
        best_dist: int
            The smallest distance between the original start and end node
            for the initial problem that you are trying to solve
        best_path: list of strings
            The shortest path found so far between the original start
            and end node.
    Returns:
        A tuple with the shortest-path from start to end, represented by
        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
        where there exists an edge from n_i to n_(i+1) in digraph,
        for all 1 <= i < k and the distance of that path.

        If there exists no path that satisfies max_total_dist and
        max_dist_outdoors constraints, then return None.
    """
    if not digraph.has_node(Node(start)) or not digraph.has_node(Node(end)):
        raise ValueError('Start or end node, or both not in graph')

    current_path = path[0] + [start]
    path[0]="This line doesn't change a thing, if I use 'current_path', but why?!"
#    path[0] = path[0] + [start]

    if start == end:
        return [current_path, path[1], path[2]]
#        return path

    edges = digraph.get_edges_for_node(Node(start))
    for edge in edges:
        next_node = str(edge.get_destination())

        if next_node not in current_path: #avoiding cycles
#        if next_node not in path[0]: #avoiding cycles

            new_tot = path[1] + edge.get_total_distance()
            new_out = path[2] + edge.get_outdoor_distance()
            if (best_dist==None or best_dist>=new_tot) and new_out<=max_dist_outdoors:

                new_path=get_best_path(digraph, next_node, end, [current_path,new_tot,new_out], \
#                new_path=get_best_path(digraph, next_node, end, [path[0],new_tot,new_out], \
                                                    max_dist_outdoors, best_dist, best_path)

                if new_path != None:
                    best_path = new_path[0]
                    best_dist = new_path[1]
    if best_path == None:
        return None
    return [best_path, best_dist]

我在这里玩弄了这个想法，但正如我所预料的，输入列表会发生变异。那么，为什么大写中的“路径”列表没有发生变异呢？

def foo_mutating(bar):
    bar[0] = bar[0] + [1]
    print('bar inside foo:', bar)
    if len(bar[0]) == 5:
        return bar
    return foo_mutating(bar)

def foo_nonmut(bar):
    temp_bar0 = bar[0]+[1]
    print('bar inside foo:', bar)
    if len(temp_bar0) == 5:
        return [temp_bar0, bar[1], bar[2]]
    return foo_nonmut([temp_bar0, bar[1], bar[2]])

def test():
    print('-----TESTING NON-MUTATING----')
    bar_init = [[], 22, 33]
    print('bar_init:', bar_init)
    new_bar = foo_nonmut(bar_init)
    print('new_bar:', new_bar)
    print('bar_init:', bar_init)
    print('\n')
    print('-----TESTING MUTATING----')
    bar_init = [[], 22, 33]
    print('bar_init:', bar_init)
    new_bar = foo_mutating(bar_init)
    print('new_bar:', new_bar)
    print('bar_init:', bar_init)

test()

指纹：

-----TESTING NON-MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[], 22, 33]

-----TESTING MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[1, 1, 1, 1, 1], 22, 33]

Answer 1

为什么这个递归不改变输入列表？

因为它不是用输入列表调用的，因此无法对其进行变异。

当您进行递归调用时(我对其进行了重新格式化)：

# "non-mutating" approach, as in the original code
new_path = get_best_path(
    digraph, next_node, end, [current_path,new_tot,new_out],
    max_dist_outdoors, best_dist, best_path
)

# "mutating" approach, using the commented-out line
new_path=get_best_path(
    digraph, next_node, end, [path[0],new_tot,new_out],
    max_dist_outdoors, best_dist, best_path
)

尝试改变路径的算法，会创建一个传递给递归调用的新列表，因此不会发生变异。与玩具示例对比：

# "non-mutating" recursive call
return foo_nonmut([temp_bar0, bar[1], bar[2]])

# "mutating" recursive call
return foo_mutating(bar)
# Notice, it does not make a new list.

通常，在不依赖变异的情况下，递归算法更容易推理。您可能还会发现，通过使用某种类来表示路径，您可以获得更清晰、更容易理解的代码。然后，您可以为“创建一个新路径并将指定的节点追加到节点名称列表”和“使用修改后的距离数据创建一个新路径”提供该类非变异方法。(或者更好的情况是--同时给它提供获取所有必要数据的Edge实例)。

类似于：

class Path:
    def __init__(self, names, distance, outdoor):
        self._names, self._distance, self._outdoor = names, distance, outdoor

    def __contains__(self, node):
        return node in self._names

    def with_edge(self, edge):
        return Path(
            # incidentally, you should be using `property`s instead of methods
            # for this Edge data.
            self._names + [edge.get_destination()],
            self._distance + edge.get_total_distance(),
            self._outdoor + edge.get_outdoor_distance()
        )

    def better_than(self, other, outdoor_limit):
        if self._outdoor <= outdoor_limit:
            return False
        best_distance = other._distance
        return best_distance is None or best_distance >= self._distance

    def end(self): # where we start recursing from during pathfinding.
        return self._names[-1]

现在我们可以做更多的事情了：

# instead of remembering best_path and best_dist separately, we'll just
# use a Path object for best_path, and we can ignore the outdoor distance
# when interpreting the results outside the recursion.
edges = digraph.get_edges_for_node(Node(start))
for edge in edges:
    if edge.get_destination() in path:
        continue
    candidate = path.with_edge(edge)
    if candidate.better_than(best_path, max_dist_outdoors):
        # We can remove some parameters from the recursive call,
        # because we can infer them from the passed-in `path`.
        new_path = get_best_path(digraph, end, path, max_dist_outdoors, best_path)
        if new_path is not None:
            best_path = new_path