Variable scoping error during recursion in Python

Question

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

stackoverflow.com/questions/4030968

user479870
– user479870

2011-11-20 15:30:18 +00:00
Commented Nov 20, 2011 at 15:30 — user479870
– user479870, Commented Nov 20, 2011 at 15:30

yak · Accepted Answer · 2011-11-20 17:26:37Z

3

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.

edited Nov 20, 2011 at 17:26

answered Nov 20, 2011 at 17:14

yak

9,1012 gold badges34 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Yarin Over a year ago

For some supporting info on why this works, take a peak at Python Functions: Assignments And Scope

yak Over a year ago

Had a look at that page. Simply put, n[0]=n[0]+1 isn't creating a local variable. It more or less expands to n.__setitem__(0, n.__getitem__(0)+1) which shows that n is only referenced, never assigned to, much like output_list.append() in my code.

Yarin Over a year ago

Exactly- it's the whole bare-name referencing he's talking about (Yak I know you get it, the link was for others who might want some extra explanation.) Good stuff.

Fred Foo · Accepted Answer · 2011-11-20 15:33:53Z

1

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

answered Nov 20, 2011 at 15:33

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

2 Comments

Yarin Over a year ago

How come nodes doesn't need global?

Fred Foo Over a year ago

nodes isn't being assigned to in the function.

David Heffernan · Accepted Answer · 2011-11-20 17:27:54Z

1

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.

edited Nov 20, 2011 at 17:27

answered Nov 20, 2011 at 15:36

David Heffernan

616k46 gold badges1.1k silver badges1.5k bronze badges

5 Comments

Yarin Over a year ago

David- thanks- but can you explain why I am able to access the nodes object without passing it?

David Heffernan Over a year ago

Because you are reading from it and not writing to it. If you assign to a global you have to tell the interpreter whether or not the name is a global or a local.

Yarin Over a year ago

David- This won't work. When I pass output as a parameter, it is not accessible by the outer functions- in your code example the output string never gets built up.

6502 Over a year ago

This would not work. Strings in Python are immutable: you cannot pass a string to a function and have the function changing the string.

David Heffernan Over a year ago

@6502 Drat! The basic principle is correct, but the extra return variable gets in the way here.

Collectives™ on Stack Overflow

Variable scoping error during recursion in Python

3 Answers 3

3 Comments

2 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related