CODEWITHSUNDEEP
pythonlistpython-2.7recursionscope
KGo
KGo

Reputation: 20064

Trying to build a list using recursion. Value in global list doesn't change

So I'm doing a problem, and I use a recursive solution. For simplicity, let's say the problem is that I need to find all anagrams of a given string. (The problem is much complicated, but this is enough to illustrate what I'm doing).

I am using recursion to do this.

all_anagrams = []

def main():
    ...
    ...
    get_anagrams() # calls a method that appends anagrams to list all_anagrams
    print all_anagrams

and the method get_anagrams is:

def get_anagrams(user_word, anagram, words, inventory):
'''
Finds all anagrams for the given user_word.
'''
    if len(inventory) == 0:
        all_anagrams.append(anagram)
    else:
        for choice in words:
                if len(choice) <= len(inventory) and choice in inventory:
                anagram.append(choice)
                inventory.subtract(choice)
                get_anagrams(user_word, anagram, words, inventory)
                    anagram.pop()
                    inventory.add(choice)

all_anagrams is supposed to be a nested list, where each sub-list is composed of some words.

Now get_anagrams should change the global value of all_anagrams but it doesn't. In main, it prints [[], [], [], [], [], []], but within the method it prints the correct list.

Consider this for example:

>>> a_list = []
>>> def change_list(some_list):
...     some_list.append(1)
...     some_list.append(2)
...     
>>> 
>>> change_list(a_list)
>>> a_list
[1, 2]

I've tried defining the list as a global list, or passing the list as a parameter since any changes to list made by callee should be reflected in the caller too. But nothing worked.

Why is it so? How do I fix it?

Upvotes: 0

Views: 108

Answers (1)

thefourtheye
thefourtheye

Reputation: 239573

The actual problem is with the append and pop. When you do

all_anagrams.append(anagram)

You are adding the reference to anagram to all_anagrams. But, when the recursion unwinds, you are popping the values from anagram. Thats why empty lists are printed in main. The immediate fix would be like this

            if len(choice) <= len(inventory) and choice in inventory:
            inventory.subtract(choice)
            get_anagrams(user_word, anagram + [choice], words, inventory)
            inventory.add(choice)

And as e-satis suggested, please avoid using global variables and pass all_anagrams as one of the parameters.

Upvotes: 3

Related Questions