Python，回溯期间返回语句

Question

我做了一点实验，发生了一些我认为没有预料到的事情。这个问题是基于递归和第7行注释的返回语句

def twentyone(nums, stack = [], answer = set()):
    for index, num in enumerate(nums):
        new_stack = stack + [num]
        total = sum(new_stack)
        if total == 21:
            answer.add(tuple(new_stack))
            #return
        elif total < 21:
            twentyone(nums[index + 1:], new_stack, answer)
    return answer

user_input = input()
list_format = [int(x) for x in user_input.split()]
answer = twentyone(list_format)

if len(answer) == 0:
    print("No combination of numbers add to 21")
for solution in answer:
    print("The values ", end = "")
    for number in solution:
            print("{} ".format(number), end = "")
    print("add up to 21")

我的问题是，在使用示例输入“1 9 11 5 6”的测试期间，如果我有返回语句。输出仅为“值1 9 11总计21”，但如果没有return语句，输出为“值1 9 11总计21，值1 9 5 6总计21”。我想知道是否有什么可以解释为什么，我认为return语句会简单地“加速”结束这个方法的递归实例，而不是简单地跳过它无法到达的其他代码行，因为我已经将元组添加到可变集合中，它会被添加到其他递归实例中，因此没有问题。但我当然错了。

Answer 1

该return语句导致for循环过早终止，因此它可能无法在该特定递归深度找到所有可能的解决方案。

我们可以通过向跟踪循环索引的函数添加一个额外的列表来看到这一点。请注意，我给index一个默认值无-这是避免默认可变参数陷阱的标准方法。

def twentyone(nums, stack = [], answer = set(), indices = None):
    if indices is None:
        indices = []
    for index, num in enumerate(nums):
        new_stack = stack + [num]
        total = sum(new_stack)
        if total == 21:
            print(indices + [index], new_stack)
            answer.add(tuple(new_stack))
            #return
        elif total < 21:
            twentyone(nums[index + 1:], new_stack, answer, indices + [index])

    return answer

user_input = '1 9 11 5 6 3 7'
list_format = [int(x) for x in user_input.split()]
answer = twentyone(list_format)
print('\n', answer)

输出

[0, 0, 0] [1, 9, 11]
[0, 0, 1, 0] [1, 9, 5, 6]
[0, 1, 1, 0] [1, 11, 6, 3]
[1, 1, 2] [9, 5, 7]
[2, 2, 0] [11, 3, 7]
[3, 0, 0, 0] [5, 6, 3, 7]

 {(9, 5, 7), (1, 11, 6, 3), (1, 9, 5, 6), (1, 9, 11), (5, 6, 3, 7), (11, 3, 7)}

如果我们取消注释返回，我们将得到以下输出：

[0, 0, 0] [1, 9, 11]
[0, 1, 1, 0] [1, 11, 6, 3]
[1, 1, 2] [9, 5, 7]
[2, 2, 0] [11, 3, 7]
[3, 0, 0, 0] [5, 6, 3, 7]

 {(9, 5, 7), (5, 6, 3, 7), (1, 11, 6, 3), (1, 9, 11), (11, 3, 7)}

索引中缺少[0,0,1,0]，这意味着[0,0,0]的for循环提前终止。

正如我前面提到的，使用可变对象作为默认参数可能是危险的。这在“最小惊讶”和可变默认论点中得到了广泛讨论。

在这段代码中，您不会遇到问题，因为只有一个调用twentyone使用默认参数，递归调用提供显式参数。但是，如果您的呼叫代码在另一个用户输入列表中第二次呼叫了twentyone，那么默认的answer仍将保留上次呼叫中收集的项目。堆栈列表是安全的，因为您从未对其进行变异。

请注意，默认可变参数的行为并不总是一个陷阱。它对于实现缓存非常有用；例如，请参见我对Python中斐波那契的回答。

FWIW，这里有一个版本的twentyone，它没有默认的可变参数问题。我还更改了stack

def twentyone(nums, stack=(), answer=None):
    if answer is None:
        answer = set()
    for index, num in enumerate(nums):
        new_stack = stack + (num,)
        total = sum(new_stack)
        if total == 21:
            answer.add(new_stack)
        elif total < 21:
            twentyone(nums[index + 1:], new_stack, answer)

    return answer

另一种实现方法是作为递归生成器。这样我们就不需要回答，我们只需要找到解决方案就可以了。

def twentyone(nums, stack=()):
    for index, num in enumerate(nums):
        new_stack = stack + (num,)
        total = sum(new_stack)
        if total == 21:
            yield new_stack
        elif total < 21:
            yield from twentyone(nums[index + 1:], new_stack)

user_input = '1 9 11 5 6 3 7'
list_format = [int(x) for x in user_input.split()]
for t in twentyone(list_format):
    print(t)

输出

(1, 9, 11)
(1, 9, 5, 6)
(1, 11, 6, 3)
(9, 5, 7)
(11, 3, 7)
(5, 6, 3, 7)

这样做的缺点是，如果nums中存在重复项，那么我们会得到重复的解决方案。但我们可以通过在set（）中运行生成器轻松绕过这一问题：

print(set(twentyone(list_format)))

输出

{(9, 5, 7), (1, 11, 6, 3), (1, 9, 5, 6), (1, 9, 11), (5, 6, 3, 7), (11, 3, 7)}

然而，这只是消除了精确的重复，它并没有摆脱作为先前解决方案排列的解决方案。为了使它完全万无一失，我们需要对输出元组进行排序。

def twentyone(nums, stack=()):
    for index, num in enumerate(nums):
        new_stack = stack + (num,)
        total = sum(new_stack)
        if total == 21:
            yield tuple(sorted(new_stack))
        elif total < 21:
            yield from twentyone(nums[index + 1:], new_stack)

user_input = '1 9 5 11 5 6 5'
list_format = [int(x) for x in user_input.split()]
print(set(twentyone(list_format)))

输出

{(1, 9, 11), (1, 5, 6, 9), (5, 5, 11), (5, 5, 5, 6)}