Python recursive function seems to lose some variable values

Question

I have 4x4 table of letters and I want to find all possible paths there. They are candidates for being words. I have problems with the variable "used" It is a list that includes all the places where the path has been already so it doesn't go there again. There should be one used-list for every path. But it doesn't work correctly. For example I had a test print that printed the current word and the used-list. Sometimes the word had only one letter, but path had gone through all 16 cells/indices.

The for-loop of size 8 is there for all possible directions. And main-function executes the chase-function 16 times - once for every possible starting point. Move function returns the indice after moving to a specific direction. And is_allowed tests for whether it is allowed to move to a certain division. sample input: oakaoastsniuttot. (4x4 table, where first 4 letters are first row etc.) sample output: all the real words that can be found in dictionary of some word In my case it might output one or two words but not nearly all, because it thinks some cells are used eventhough they are not.

def chase(current_place, used, word):

   used.append(current_place)   #used === list of indices that have been used
   word += letter_list[current_place]
   if len(word)>=11:
       return 0
   for i in range(3,9):
       if len(word) == i and word in right_list[i-3]:  #right_list === list of all words
        print word
        break
   for i in range(8):
      if is_allowed(current_place, i) and (move(current_place, i) not in used):    
          chase(move(current_place, i), used, word)

Its not immediately apparent from your explanation what you are trying to do. Could you provide a sample input and output? — Paul Seeb
– Paul Seeb, Commented Jan 25, 2013 at 19:15
Input is for example oakaoastsniuttot. That is a string representation of 4X4 table of those same strings. And output should be all the real words(that can be found in dictionary) that you can get. in a smaller table like this: OYN ETA MSK You could find for example Y E S The input/output didn't show as I wanted. But the next letter can be in any 8 directions(up, down, left, right, downleft, downright, upright, upleft) — Teemu Leivo
– Teemu Leivo, Commented Jan 25, 2013 at 19:23

NPE · Accepted Answer · 2013-01-25 19:34:30Z

2

The problem is that there's only one used list that gets passed around. You have two options for fixing this in chase():

Make a copy of used and work with that copy.
Before you return from the function, undo the append() that was done at the start.

answered Jan 25, 2013 at 19:34

NPE

503k114 gold badges970 silver badges1k bronze badges

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

5 Comments

Teemu Leivo Over a year ago

Do you mean I should do like this: used2 = used and then pass along that used2 list to the next chase?

NPE Over a year ago

@TeemuLeivo: Almost. used2 = used[:] (without the [:], used2 would refer to the same list as used).

Teemu Leivo Over a year ago

That solved it! Thank you! Actually I had before tried the used2=used fix, but as you explained, that didn't work. As a more theoretical question: If used is a local variable, so why is it then available in other functions?

NPE Over a year ago

@TeemuLeivo: used contains a reference to the list. Even though the reference is local, the list itself is not. Anyone modifying the list through their local reference are still modifying the one shared list.

Teemu Leivo Over a year ago

Thank you! That cleared it up a lot. Now understand a bit better what happens "under the hood"

Collectives™ on Stack Overflow

Python recursive function seems to lose some variable values

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related