Python递归地将列表深度复制到自身n次

Question

我需要将list的深层副本(不是引用)递归地追加n次，例如对于

n=0 -> []
n = 1 -> [[]]
n=2 -> [[], [[]]] 
and so forth. 

这是我到目前为止写的:

def magic_list(n: int) -> List[Any]:
#take only positive numbers
assert(n>=0)

if n == 0:
return []
else:
return magic_list_helper(0, n, [])

的主函数，我必须保持这个def签名完全相同(只接受n:int)。这是我写的辅助函数:

def magic_list_helper(index: int,threshold:int ,lst:List[Any]) -> List[Any]:
if index >= threshold:
return lst

else:

# temp_lst = deepcopy(lst)
# lst.append(temp_lst)
return magic_list_helper(index + 1, threshold, lst)

对于这个问题，我不能使用copy.deepcopy或任何其他外部库(这就是为什么它与#，没有它它工作)，我找不到一个没有深度拷贝的在线解决方案。此外，我不能在列表上使用列表理解，切片或任何O(n)操作(我可以使用追加)。希望你能帮助我，提前谢谢。

Answer 1

你可以试试这个。不确定是不是正确的。

l=[]
n=2
for i in range(n):
l.append(l.copy())
print(l)

Answer 2

你不需要复印。每个调用都可以使用一个执行n次的列表推导式，递归地调用自己。列表推导式创建具有适当长度的新列表。

你甚至不需要检查基本情况，因为当n == 0时，列表推导式将返回一个空列表。

def magic_list(n: int) -> List[Any]:
return [magic_list(x) for x in range(n)]
for i in range(5): print(magic_list(i))
[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]
[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]

Answer 3

使用归纳推理是递归解决问题的基础-

1. 如果n小于等于零，则做功。返回空结果，[]
2. (感应)n至少为1(正)。找到子问题magic_list(n - 1)的结果，并将其连接到同一子问题[magic_list(n - 1)]的单例列表

# write
def magic_list(n):
if n <= 0: return []
return magic_list(n - 1) + [magic_list(n - 1)]

递归是函数式的遗产，因此将它与函数式风格结合使用会产生最好的结果。这意味着要避免突变(.append)、变量重赋和其他副作用。

# test
for n in range(5):
print(magic_list(n))

# output
[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]
[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]

在上面的程序中，可以看到子问题magic_list(n - 1)被计算了两次。通过将结果赋值给一个变量

，我们将工作量减半。

# optimize
def magic_list(n):
if n == 0: return []
m = magic_list(n - 1) # ✏️
return m + [m]        # 💯