Pythonで全系列の探索をdfsで行い、全系列を列挙する場合、その全系列を戻り値として呼び出し側に返して、呼び出し側で利用する場合がある。列挙するのが数列（リスト）の場合、dfsの再帰関数で数列（リスト）を引数として渡しながら、末端までいったらそこまでの数列を、戻り値にappendしていって、全系列のリストを呼び出し側に返したい。

このとき、列挙した数列（リスト）を戻り値にappendするところで、Pythonでのリストのコピーについて知っておくべきことがあった。

Pythonでのリストの代入とコピー

Pythonでリストを代入する場合、

a = [0, 2, 3]
b = a
a[0] = 3
print(b)

の結果は、

[3, 1, 2]

となる。
b = a で初期のa（[0, 1, 2]）を b に代入しているが、代入では値をコピーせずに同じオブジェクトを参照・共有するため、aを変更するとbも変更されてしまっている。
aの"中身"のコピーをbに代入するには、

b = list(a)

や

b = a[:]

のようにして、新たにaの中身をコピーしたlistオブジェクトを作ってbに代入しないといけない。

dfsで数列（リスト）を列挙する

dfsで数列を列挙して、その結果を戻り値に反映させる場合を考えてみる。例として、m進数n桁の数列を列挙する。これをdfsで実装してみると、

def dfs(k, n, m, f):
    if k == n:
        print(f)
        return
    for j in range(m):
        f[k] = j
        dfs(k+1, n, m, f)
    return

n = 2
m = 3
dfs(0, n, m, [0]*n)

このようにすることで、画面にm桁の数列をmⁿ個出力することができる。

[0, 0]
[0, 1]
[0, 2]
[1, 0]
[1, 1]
[1, 2]
[2, 0]
[2, 1]
[2, 2]

では、呼び出し側に戻り値として列挙した数列のリストを返すにはどうするか。
列挙した数列を、戻り値（リスト）にappendしていってみると、

def dfs(k, n, m, f, v):
    if k == n:
    	v.append(f)
        return v
    for j in range(m):
        f[k] = j
        v = dfs(k+1, n, m, f, v)
    return v

n = 2
m = 3
v = dfs(0, n, m, [0]*n, [])
for f in v:
    print(f)

のようになりそうである。ところが、この出力は、

[2, 2]
[2, 2]
[2, 2]
[2, 2]
[2, 2]
[2, 2]
[2, 2]
[2, 2]
[2, 2]

となってしまう。

Pythonの関数への引数の渡し方

関数の引数は、仮引数に実引数を代入して値を共有するため、引数のリストにappendし、その後に元のリストの値を変更すると、appendしたリストの値も変化してしまう。上記の例では、dfsが最後まで進んだときの最後の数列が[2, 2]なので、それまでにappendした数列の中身がすべて[2, 2]になってしまっている。

リストにappendするときには、リストをそのままappendするのではなく、リストのコピーを作成してappendする必要がある。例えば、

def dfs(k, n, m, f, v):
    if k == n:
    	v.append(list(f))
        return v
    for j in range(m):
        f[k] = j
        v = dfs(k+1, n, m, f, v)
    return v

n = 2
m = 3
v = dfs(0, n, m, [0]*n, [])
for f in v:
    print(f)

のようにすると、appendされたリストが、その後のリストの操作に影響を受けなくなる。結果は、以下の通り。

[0, 0]
[0, 1]
[0, 2]
[1, 0]
[1, 1]
[1, 2]
[2, 0]
[2, 1]
[2, 2]