递归函数的后续问题，解决了在游戏中获得一定数量点的所有可能方法

Question

原始问题（已解决）：假设您可以在一个简化的足球计分系统中得分 {2, 3, 7} 分，那么在给定分数的情况下，您可以通过哪些方式得分？在此处链接到该问题我试图围绕这些递归函数在下面的代码中维护分数和结果变量的方式来思考。代码解决方案（由 ggorlen 提供）：def find_scoring(points, ways_to_score=[2, 3, 7]):    def score_finder(points, scores, result):        if points == 0:            result.append(scores[:])        elif points > 0:            for val in ways_to_score:                scores.append(val)                score_finder(points - val, scores, result)                scores.pop()        return result    return score_finder(points, [], [])这很好用，完全回答了我原来的问题。但是在阅读了 Elements of Programming Interviews (Python) 中的一些问题后，我决定尝试一下我通过结果和分数列表的方式。我模拟了作者的一项技术，每次递归调用函数时不传递结果列表，而是分配空列表的默认值：def find_scoring2(points, ways_to_score=[2, 3, 7]):    def score_finder(points, scores, result = []):        if points == 0:            result.append(scores[:])        elif points > 0:            for val in ways_to_score:                scores.append(val)                score_finder(points - val, scores)                scores.pop()        return result    return score_finder(points, [])这产生了相同的结果，并且这个想法来自 EPI 第 235 页（生成平衡括号）。然后我决定改变分数变量的创建方式，以摆脱从列表中弹出的需要。我不理解代码，但我再次从同一本书中复制了这个想法。def find_scoring3(points, ways_to_score=[2, 3, 7]):    def score_finder(points, scores, result = []):        if points == 0:            result.append(scores[:])        elif points > 0:            for val in ways_to_score:                #scores.append(val)                score_finder(points - val, scores + [val])                #scores.pop()        return result    return score_finder(points, [])所以我的问题是： 1. 我如何围绕每次设置为空列表的结果变量，并且仍然产生正确的解决方案？是否有一些视频或参考资料可以帮助我了解它是如何工作的？2. 为什么当我从追加切换到仅向列表中添加值时，分数变量的行为会发生变化？

Answer 1

第二个和第三个版本基于Python 默认参数的令人惊讶的行为意外地工作：

>>> def foo(bar=[]):

...     bar.append(42)

...     return bar

...

>>> foo()

[42]

>>> foo()

[42, 42]

>>> foo()

[42, 42, 42]

发生了什么？好吧，什么时候foo被定义，什么时候bar = []被创建。未来的调用不会像预期的那样设置bar为新的空列表，而是分配bar给原始列表的别名，该别名不断累积42s。

这是非常违反直觉的，因为我们通常希望这样的函数是无状态的并且像这样工作：

>>> def foo(bar=""):

...     bar += "42"

...     return bar

...

>>> foo()

'42'

>>> foo()

'42'

>>> foo()

'42'

现在让我们foo转到 的内部函数baz：

>>> def baz():

...     def foo(bar=[]):

...         bar.append(42)

...         return bar

...     return foo()

...

>>> baz()

[42]

>>> baz()

[42]

>>> baz()

[42]

事实证明，在这种情况下，foo每次调用 时都会从头开始创建baz，以及它的bar = []列表。baz返回时，被foo销毁，因为它只是baz的堆栈帧中的一个局部变量，以及bar.

为了使这一点更明显，这里有一个实验：

>>> def foo(bar=print("bar defined")): pass

...

bar defined

>>> foo()

>>> foo()

>>> foo()

>>> def baz():

...     def foo(bar=print("bar defined")): pass

...

>>> baz()

bar defined

>>> baz()

bar defined

>>> baz()

bar defined

印刷品应该很清楚发生了什么。但如果不是，这里有一个递归版本，它类似于您的函数，因为它通过在默认参数上“滥用”别名来跨堆栈帧构建结果列表：

>>> def foo(i=4, bar=[]):

...     if i:

...         bar.append(i)

...         return foo(i - 1)

...     return bar

...

>>> foo()

[4, 3, 2, 1]

但它在JS中失败了：

> const foo = (i=4, bar=[]) => {

... if (i) {

..... bar.push(i);

..... return foo(i - 1);

..... }

... return bar;

... };

undefined

> foo();

[]

和红宝石：

irb(main):023:0> def foo(i=4, bar=[])

irb(main):024:1>   if i > 0

irb(main):025:2>     bar.push(i)

irb(main):026:2>     return foo(i - 1)

irb(main):027:2>   end

irb(main):028:1>   return bar

irb(main):029:1> end

=> :foo

irb(main):030:0> foo

=> []

每次调用foo()缺少bar参数的地方都会获得一个分配给的新数组（列表）bar。我可以展示其他语言示例，但请相信 Python 在将对象视为默认参数方面非常独特。

考虑到所有这些，“正确的”递归调用应该是score_finder(points - val, scores, result)（类似于return foo(i - 1, bar)--try this out on the JS/Ruby version if you want），它在result函数被调用一次后填充默认参数。

这解释了我编写原始代码的动机——我只是通过def foo(bar=[])完全避免默认模式来跳过所有奇怪的事情（def foo(bar=42)尽管对于像这样的原语来说没问题）。

至于你的第二个问题，scores + [val] 看起来更干净，因为没有append/ pop/ [:]，但它实际上更慢且更占用内存。不是创建一个通过引用在调用堆栈中传递的列表（并且仅在结果准备好时从头到尾复制），而是find_scoring3为每个递归调用帧创建一个全新的列表（很多额外的工作）。这也意味着find_scoring3正在执行不必要的复制（scores[:]--try 删除切片）。

Python 的一个缺点是它提供了许多易于 (ab) 使用的 O(n) 列表操作，例如[:], in list，list + []如果使用不当可能会导致时间复杂度上升。