我正在练习解决递归和回溯练习。
我在打印列表列表中的所有笛卡尔积时遇到问题，其中每个子列表仅包含不同的字符。当然，如果任何一个子列表为空，则最终产品为空列表。
我立即想到了递归/回溯地解决它。
我很不擅长递归-人们给我的建议是：
将递归视为一个黑盒，只考虑一些适当的基本情况，并归纳地假设您得到n-1的答案，然后进行递归。
所以这就是我的想法
“基本情况是什么？”当列表列表为空时-我将打印一个空列表。
如果没有，我将返回第一个子列表的第一个字符，以及从下一个子列表到列表的递归调用。
def cartesian_product(lst):
if len(lst)==0:
return []
for c in cartesian_product(lst[1:]):
for s in c:
return [lst[0][0]] + [s]
我猜这里的问题是因为我没有保存当前的子列表，而我总是在第一个子列表中。
但是，出现“ NoneType”错误，我不知道为什么。
我如何知道何时需要功能助手？我什么时候可以解决我如何描述人们告诉我的？
最佳答案
首先，尽管这是递归，但我不认为它会回溯，因为我们不会集合起来，然后可能会拒绝候选解决方案。我们从概念上将空列表视为基本情况，但是Python的循环逻辑不会在空列表上运行。因此，相反，我们使用两种基本情况，一个空的参数列表和仅一个子列表的参数列表。
如果我们的参数只有一个子列表[1, 2, 3]，则结果为[[1], [2], [3]]，否则解决方案是将初始子列表的每个成员附加到对其余部分进行递归调用的结果的（副本的）开头子列表：
def cartesian_product(array):
product = []
if array: # avoid empty base case
head, *tail = array
if tail: # not a base case
for t in cartesian_product(tail):
for h in head:
product.append([h] + t)
else: # one list base case
product = [[h] for h in head]
return product
此逻辑还为我们提供了所需的行为，即空列表作为任何参数子列表出现时会导致返回空列表。