时间戳

首页 > 解决方案 > 递归中的python列表是否不会更改为其先前的值？

python - 递归中的python列表是否不会更改为其先前的值？

问题描述

假设这是我通过 dfs 稀疏树的函数，并且有一个名为 c 的变量用于存储节点数和一个列表调用 te。我的树是 {1:[2,3],2:[1],3:[1]} 根是 1。te=[1] c=1 根是 2。te=[1,2] c=2 root 是 3 te=[1,2,3] c=2 .我的函数是 dfs(i,te,c) 明显 c 回滚但列表没有变成 [1,3]

def dfs(node,visited,te,c=0):
        if visited[node]==0:
            visited[node]=1
            te.append(node)
            c=c+1
            print(te)
            if node in king:
                for nei in king[node]:
                    if visited[nei]==0:
                        dfs(nei,visited,te,c)

标签： pythonlistrecursion

解决方案

在递归期间，值永远不会“变回”到以前的值。由于整数是不可变的，因此在每个递归步骤中为它们分配一个新值（替换旧值）c=c+1：. 由于列表是可变的，因此它们可以在每个递归步骤中将一个元素附加到现有值（修改旧值）te.append(node)：.

最简单的更改是也为列表创建并分配一个新值：

def dfs(node,visited,te,c=0):
    if visited[node]==0:
        visited[node]=1
        te = te + [node]  # create new list on each recursive step
        c = c + 1
        print(te)
        if node in king:
            for nei in king[node]:
                if visited[nei]==0:
                    dfs(nei, visited, te, c)

通过使用元组而不是列表可以避免此类错误。不能追加元组。

或者，在传递列表时创建一个副本：

def dfs(node,visited,te,c=0):
    if visited[node]==0:
        visited[node]=1
        te.append(node)
        c = c + 1
        print(te)
        if node in king:
            for nei in king[node]:
                if visited[nei]==0:
                    # copy mutable value before passing it on
                    dfs(nei, visited, te.copy(), c)

或在完成后删除附加值：

def dfs(node,visited,te,c=0):
    if visited[node]==0:
        visited[node]=1
        te.append(node)
        c = c + 1
        print(te)
        if node in king:
            for nei in king[node]:
                if visited[nei]==0:
                    dfs(nei, visited, te, c)
        te.pop()  # remove previously appended element

推荐阅读