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

Question

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?

The fun way is to use yield and yield from instead of appending to a global list. Please use the fun way; it will probably also solve your problem. — Ry-
– Ry- ♦, Commented Dec 21, 2013 at 7:07
Then yield in a loop. Also, if len(inventory) == 0 can be if inventory. — Ry-
– Ry- ♦, Commented Dec 21, 2013 at 7:11
@thefourtheye: Yes, or flip the blocks. (It looks better that way!) — Ry-
– Ry- ♦, Commented Dec 21, 2013 at 7:14

thefourtheye · Accepted Answer · 2013-12-21 09:27:33Z

3

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.

edited Dec 21, 2013 at 9:27

answered Dec 21, 2013 at 7:21

thefourtheye

241k53 gold badges466 silver badges505 bronze badges

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

2 Comments

Bite code Over a year ago

+1. Also, pass all_anagrams as a parameter, don't use a global variable. And returns it.

thefourtheye Over a year ago

@e-satis Thanks :) Added a note to use all_anagrams as a parameter instead of using it as a global variable.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related