CODEWITHSUNDEEP
pythonrecursionscope
Yarin
Yarin

Reputation: 183989

Variable scoping error during recursion in Python

The following code recursively processes a list of dictionaries into a tree while building an HTML output string. I'm getting a scope access error when trying to access the output string variable from within the recursing function. However, it has no problem accessing the nodes list object in the same scope- and in fact the function worked fine before I added the output var. What's the deal here?

Sample: http://ideone.com/Kg8ti

nodes = [ 
{ 'id':1, 'parent_id':None, 'name':'a' },
{ 'id':2, 'parent_id':None, 'name':'b' },
{ 'id':3, 'parent_id':2, 'name':'c' },
{ 'id':4, 'parent_id':2, 'name':'d' },
{ 'id':5, 'parent_id':4, 'name':'e' },
{ 'id':6, 'parent_id':None, 'name':'f' }
]

output = ''

def build_node(node):
    output += '<li><a>'+node['name']+'</a>'
    subnodes = [subnode for subnode in nodes if subnode['parent_id'] == node['id']]
    if len(subnodes) > 0 : 
        output += '<ul>'
        [build_node(subnode) for subnode in subnodes]
        output += '</ul>'
    output += '</li>'
    return node

output += '<ul>'
node_tree = [build_node(node) for node in nodes if node['parent_id'] == None]
output += '</ul>'   

import pprint
pprint.pprint(node_tree)

Error:

Traceback (most recent call last):
  File "prog.py", line 23, in <module>
    node_tree = [build_node(node) for node in nodes if node['parent_id'] == None]
  File "prog.py", line 13, in build_node
    output += '<li><a>'+node['name']+'</a>'
UnboundLocalError: local variable 'output' referenced before assignment

Upvotes: 1

Views: 953

Answers (3)

David Heffernan
David Heffernan

Reputation: 613592

Whilst you can use a global declaration, it would be much clearer to pass output as a parameter.

Global variables are considered to bad practice and where there are good methods to avoid using them you should avail yourself of those methods.

Upvotes: 1

yak
yak

Reputation: 9041

The error stems from this:

output = ''
def add(s):
    output = output + s

which is equivalent to output+=s. The two output-s in the expanded form refer to different scopes. The assignment sets a local variable while the expression on the right references a global (because local isn't set yet).

Python detects such conflicts and throws an error.

Others have suggested using global to let Python know both output-s refer to the global scope but since you're concatenating strings here, there's an even better idiom used for this task in Python:

output_list = []
def add(s):
    output_list.append(s)
# ...
output = ''.join(output_list)

Here you're not setting a variable in the function so there's no need for global. Strings from all calls are added to a list and finally joined using '' (empty string) as separator. This is much faster than adding strings using += because strings in Python are immutable so every time you add two strings, Python has to create a new string. This introduces a lot of memory copying.

Upvotes: 3

Fred Foo
Fred Foo

Reputation: 363848

def build_node(node):
    global output
    # proceed as before

Upvotes: 1

Related Questions