如何修复Python递归函数，生成[[1],[1,2],…,[1,2,…,10]]嵌套列表？

问题描述 #

你编写了以下Python递归代码，期望生成从[1]到[1,2,...,10]的嵌套列表：

all = []
def generate(i, current):
    if i < 11:
        current.append(i)
        all.append(current)
        i+= 1
        generate(i, current)
generate(1, [])
print(all)

但实际运行后，输出的是10个完全相同的[1,2,3,4,5,6,7,8,9,10]，而非预期的逐步递增列表。

问题原因 #

Python中列表是可变对象，你每次向all里添加的都是同一个current列表的引用，而不是它的副本。递归过程中，current一直在被修改（append(i)），所以最后all里的所有元素指向的都是同一个最终被填满的列表。

修复方案 #

要解决这个问题，核心是避免向all中添加同一个列表的引用，而是每次添加当前状态的副本。以下是三种可行方案：

方案1：使用列表切片创建副本 #

修改all.append(current)为all.append(current[:])，切片操作[:]会生成一个新的列表副本：

all = []
def generate(i, current):
    if i < 11:
        current.append(i)
        all.append(current[:])  # 生成当前列表的副本添加到all
        i += 1
        generate(i, current)
generate(1, [])
print(all)

方案2：使用list()函数创建副本 #

也可以用list(current)来生成新的列表副本，效果和切片一致：

all = []
def generate(i, current):
    if i < 11:
        current.append(i)
        all.append(list(current))  # 生成当前列表的副本添加到all
        i += 1
        generate(i, current)
generate(1, [])
print(all)

方案3：递归时传递新列表（避免修改原列表） #

另一种思路是，每次递归调用时创建新的列表，不修改原current列表，从根源上避免引用共享问题：

all = []
def generate(i, current):
    if i < 11:
        new_current = current + [i]  # 创建包含新元素的新列表
        all.append(new_current)
        generate(i + 1, new_current)
generate(1, [])
print(all)

运行以上任意一种修复后的代码，都能得到预期输出：

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6, 7], [1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]

内容的提问来源于stack exchange，提问作者Stanislawstask