UnboundLocalError in recursive call of nested function

Question

I have the following Python code:

def find_words(letters):
    results = set()

    def extend_prefix(w, letters):
        if w in WORDS: results.add(w)
        if w not in PREFIXES: return
        for L in letters:
            result = extend_prefix(w + L, letters.replace(L, "", 1))
            results = results | result

    extend_prefix('', letters)
    return results

print find_words("ABCDEFGH")

When I run it, I get the following error:

Traceback (most recent call last):
  File "ExtendPrefix.py", line 44, in <module>
    print find_words("ABCDEFGH")
  File "ExtendPrefix.py", line 41, in find_words
    extend_prefix('', letters)
  File "ExtendPrefix.py", line 38, in extend_prefix
    result = extend_prefix(w + L, letters.replace(L, "", 1))
  File "ExtendPrefix.py", line 38, in extend_prefix
    result = extend_prefix(w + L, letters.replace(L, "", 1))
  File "ExtendPrefix.py", line 35, in extend_prefix
    if w in WORDS: results.add(w)
UnboundLocalError: local variable 'results' referenced before assignment

It apparently can't find results in a recursive call to extend_prefix. Why is this and how can I fix it?

Answer 1

Because you're assigning results inside of a nested function, Python assumes you're using a locally scoped variable and throws up at line 35 even though it's a valid name in a higher scope. If you were only reading the variable and not writing to it, it will oftentimes work on the higher namespace object. But as soon as an assignment operator appears, you jump to local namespace.

From Python scopes/namespaces:

A special quirk of Python is that – if no global statement is in effect – assignments to names always go into the innermost scope. Assignments do not copy data — they just bind names to objects.

To get around this, the easiest is to pass the variable you want use into the function header:

def extend_prefix(w, letters, results):
        if w in WORDS: results.add(w)
        if w not in PREFIXES: return
        for L in letters:
            extend_prefix(w + L, letters.replace(L, "", 1), results)

Also the way you wrote the function, you weren't returning a set, so the results = results | result would have blown up with results being None Type.

Answer 2

Alternatively, you wouldn't need a nested function if you used a default value of None for results and then initialized results as an empty set. It simplifies your code a bit and fixes your problem. See below...

def find_words(letters, pre = '', results = None):
    if results is None: results = set()
    if pre in WORDS: results.add(pre)
    if pre in PREFIXES:
        for L in letters:
            find_words(letters.replace(L, '', 1), pre+L, results)
    return results

It's good to see another Udacity student on StackOverflow!