Follow up question to recursive function that solves all possible ways to achieve a certain number of points in a game

Question

Original question (which has been solved): Assuming a simplified football scoring system where you can score {2, 3, 7} points, what are all the possible ways that you can score given a number of points?

Link to that question here

I am trying to wrap my head around the way these recursive functions maintain the score and results variable in the code below.

Code solution (by 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, [], [])

This works beautifully, and fully answered my original question. But after reading some problems in Elements of Programming Interviews (Python), I decided to play around with the way I pass the results and scores list. I emulated a technique by the author by not passing results list every time I call the function recursively, but instead assign a default value of the empty list:

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, [])

This produced the same results and the idea came from EPI page 235 (generating balanced parentheses).

I then decided to change the way the scores variable was created to get rid of the need to pop from the list. I didn't understand the code, but again I copied the idea from the same book.

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, [])

So my questions are: 1. How do I wrap my head around the results variable being set to the empty list each time, and still producing the right solution? Is there some video or reference that would help me see how this works? 2. Why does the behavior of the scores variable change when I switch from appending, to just adding a value to my list?

Answer 1

The second and third versions work accidentally based on the surprising behavior of Python default arguments:

>>> def foo(bar=[]):
...     bar.append(42)
...     return bar
...
>>> foo()
[42]
>>> foo()
[42, 42]
>>> foo()
[42, 42, 42]

What happened? Well, when foo was defined, bar = [] was created. Future calls do not set bar to a new empty list as might be expected, but rather assign bar to an alias of the original list, which keeps accumulating 42s.

This is pretty counter-intuitive, because we'd generally expect functions like this to be stateless and work like:

>>> def foo(bar=""):
...     bar += "42"
...     return bar
...
>>> foo()
'42'
>>> foo()
'42'
>>> foo()
'42'

Now let's move foo to an inner function of baz:

>>> def baz():
...     def foo(bar=[]):
...         bar.append(42)
...         return bar
...     return foo()
...
>>> baz()
[42]
>>> baz()
[42]
>>> baz()
[42]

It turns out that in this case, foo is created from scratch on every call of baz, along with its bar = [] list. When baz returns, foo is destroyed because it's just a local variable in baz's stack frame, along with bar.

To make this more obvious, here's an experiment:

>>> 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

The prints should make it pretty clear what's going on. But if not, here's a recursive version that is similar to your function in that it builds a result list across stack frames by "abusing" aliasing on a default parameter:

>>> def foo(i=4, bar=[]):
...     if i:
...         bar.append(i)
...         return foo(i - 1)
...     return bar
...
>>> foo()
[4, 3, 2, 1]

but it fails in, say, JS:

> const foo = (i=4, bar=[]) => {
... if (i) {
..... bar.push(i);
..... return foo(i - 1);
..... }
... return bar;
... };
undefined
> foo();
[]

and Ruby:

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
=> []

where each call to foo() that is missing the bar parameter gets a fresh array (list) assigned to bar. I can show other language examples, but take my word that Python is pretty much unique in its treatment of objects as default parameters.

With all this in mind, the "correct" recursive call should be score_finder(points - val, scores, result) (akin to return foo(i - 1, bar)--try this out on the JS/Ruby versions if you want), which fills in the default argument for result after the function has been called once.

This explains my motivation for writing the original code as I did--I just skipped all of the strangeness by avoiding the default def foo(bar=[]) pattern entirely (it's OK for primitives like def foo(bar=42) though).

---

As for your second question, scores + [val] seems cleaner, because there's no append/pop/[:], but it's actually slower and more memory-intensive. Instead of creating one list that gets passed around the call stack by reference (and copied from beginning to end only when a result is ready), find_scoring3 creates a whole new list for every recursive call frame (a lot of extra work). This also means find_scoring3 is doing an unnecessary copy (scores[:]--try dropping the slice).

A drawback of Python is that it offers a lot of O(n) list operations that are easy to (ab)use, like [:], in list, list + [] that can blow the time complexity up if used incorrectly.