Understanding Recursion "local" variable in Python

Question

I'm just learning about recursion and am trying to apply it in some for-fun, come-to-understand-it ways. (Yes, this whole thing is better done by three nested for loops)

def generate_string(current_string, still_to_place):
    if still_to_place:
        potential_items = still_to_place.pop(0)
        for item in potential_items:
            generate_string(current_string + item, still_to_place)
            #print("Want to call generate_string({}, {})".format(current_string + item, still_to_place))
    else:
        print(current_string)
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']])

If I comment out the recursive call and uncomment the print, it prints exactly what I'd hope it would be calling. However, just uncommenting the print shows that it calls an empty still_to_place array even when it should still have the [d,e,f], [g,h,i] from the "higher up" recursion I think.

What am I missing in my understanding? Thanks!

Answer 1

Right, this is the expected behavior. The reason is that still_to_place is being shared between each function call. Mutable objects in Python are 'passed by assignment', meaning that, if you pass a list to a function, that function shares a reference to the SAME list. This thread has more detail.

So, each time you call still_to_place.pop(0), you are popping the list in every recursive call. They all share the exact same list.

This behavior is not always desirable, often you want your list to be immutable. In this case, you need to pass your recursive call a modified copy of the data structure. Here's what your code would look like using the immutable approach:

def generate_string(current_string, still_to_place):
    if still_to_place:
        potential_items = still_to_place[0]
        for item in potential_items:
            generate_string(current_string + item, still_to_place[1:])
            print("Want to call generate_string({}, {})".format(current_string + item, still_to_place))
    else:
        print(current_string)
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']])

As a rule of thumb, methods on the object (e.g. .pop) will modify it in-place. Also, different languages approach mutability differently, in some language, data structures are ALWAYS immutable.

Answer 2

I outputted what I got during each iteration of generate_string and this is what I got. It's probably all confusing because nothing is behaving how you expected, but let me explain what Python is thinking.

#1st time
current_string = ""
still_to_place = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]

We start out by passing in the above data, however, as we walk through what happens, we first pop the first array ['a', 'b', 'c'], and we begin to iterate through this popped array. However because we called .pop(0), we now only have the latter part of the array, the still_to_place.pop(0) on the first recursive call that is made to generate_string()

#2nd time
current_string = "a"
still_to_place = [['d', 'e', 'f'], ['g', 'h', 'i']]

This is exactly what was in current_string and still_to_place the first time the recursive call was made. Now we are going to begin executing the function again from the beginning. We call the pop function again, removing the second array ['d', 'e', 'f']. Now we are only left with the third and final array.

#3rd time
current_string = "ad"
still_to_place = [['g', 'h', 'i']]

As we iterate through ['g', 'h', 'i'], because still_to_place is now empty. (We have just popped the last array.) Any calls to generate_string will go directly to the else clause, and we are going to be printing out the "ad" string plus the values in the array we just popped.

#4th, 5th and 6th time
still_to_place = []
current_string = "adg"

still_to_place = []
current_string = "adh"

still_to_place = []
current_string = "adi"

We now continue where the last recursive call left off, when we where going through the second time. This is where things get confusing. When we left off current_string = "a" and still_to_place was originally [['d', 'e', 'f'], ['g', 'h', 'i']], but we have since popped everything off of the array. You see, arrays behave differently than numbers or strings. All versions of an array share the same data. You change the data once, it changes it everywhere that array is used. (objects and dictionaries also behave this way.)

So with all that said still_to_place = [], and still_to_place will stay empty for the remainder of the recursive calls. potential_items still has the data that it popped of ['d', 'e', 'f']. We've already executed the 'd' string in steps #4, #5, and #6, so we can finish where we left of

#7th and 8th times
still_to_place = []
current_string = "ae"

still_to_place = []
current_string = "af"

Once again potential_items has ['a', 'b', 'c'] and we've already executed 'a'. Unlike still_to_place, potential_items is a local variable with a smaller scope. If you know how scopes work, then it will make since why we can have multiple potential_items, but it is the same still_to_place that was being used. Each time we popped an item off of still_to_place we where adding the popped result to a new potential items variable with a limited scope. still_to_place was global to the entire program, and so one change to still_to_place would cause changes that where not being anticipated.

Hopefully I made things more confusing, and not less confusing. Leave a comment on what you need more clarification on.