Recursion behavior in Python vs C# - Strange results

Question

I'm an experienced programmer but new to Python, so I don't know if what I'm seeing here is behavior specific to Python that I'm unaware of. I normally program in C++ and C# so I've included code samples in both languages to demonstrate the different results.

What I'm doing is running a recursive search function, using a state structure to record results. In C# it behaves as expected, but in Python it seems to be (as far as I can tell), not differentiating between the state that exists in current/last recursive call. I'm aware of Python managing objects by reference (as in C#) - I'm taking a deepcopy of the object before passing it further into the search function.

First up the C# version and results:

class SimState
{
    public List<string> stateDescriptions = new List<string>();
    public SimState Clone()
    {
        return new SimState() {
            stateDescriptions = new List<string>(this.stateDescriptions)
        };            
    }
}
class Program
{
    public void search_recursive(SimState state,int move,int recurseDepth)
    {
        if (recurseDepth > 2)
            return;
        state.stateDescriptions.Add(move.ToString());
        Console.WriteLine(String.Format("{0}: {1}", 
            recurseDepth,
            String.Join(",", state.stateDescriptions)));
        for(int n = 0;n < 2;n++)
        {
            var newState = state.Clone();
            this.search_recursive(newState, n + 1, recurseDepth + 1);
        }
    }
    static void Main(string[] args)
    {
        var initialState = new SimState();
        new Program().search_recursive(initialState, 0, 0);
        Console.ReadKey();
    }
}

And the results: This is what I'd expect to happen. It searches all combinations down to a max. depth of 2:

0: 0
1: 0,1
2: 0,1,1
2: 0,1,2  
1: 0,2
2: 0,2,1
2: 0,2,2

So far so good. Now, what I thought was an equivalent Python program:

import copy

class SimState:
    stateDescriptions = []

def search_recursive(state: SimState, move, recurseDepth):
    if(recurseDepth > 2):
        return
    state.stateDescriptions.append('{0}'.format(move))
    print('{0}: '.format(recurseDepth) +  ','.join(state.stateDescriptions))
    for n in range(2):
        newState = copy.deepcopy(state)
        search_recursive(newState,n + 1,recurseDepth + 1)

initialState = SimState()
search_recursive(initialState,0,0)

And the results:

0: 0
1: 0,1
2: 0,1,1
2: 0,1,1,2
1: 0,1,1,2,2
2: 0,1,1,2,2,1
2: 0,1,1,2,2,1,2

It seems as if Python is not aware of the fact that I'm passing in a completely new state (via the new deep-copied 'newState'), and instead updating the existing 'state' from the previous recursive call. I'm aware of the post on SO ""Least Astonishment" and the Mutable Default Argument") but that seems to be referring specifically to default arguments, which are not in use here.

I'm using Python 3.6 from within Visual Studio 2017.

Am I missing something obvious? Thanks

You've just pointed me in the right direction. I thought my definition of stateDescriptions[] in the SimState class was the equivalent of declaring a member variable, but as you mentioned it's a static class attribute. I replaced it with an __init__ method and assigning self.stateDescriptions = [] and it now works as I'd expect. Thanks for the quick answer. re why did I use a class? That was just to provide a cut-down example based on the actual problem I'm trying to solve, where the SimState is far more complex. — Dan James, Dec 12 '17 at 00:09
Makes sense. Anyway, I went ahead and just added an answer. Note, Python is a rather dynamic language, and it's object model is a bit different than your typical statically-typed OOP language. For example, `self.stateDescriptions` will first check the instance namespace, and if it doesn't find it, it will check the class-namespace, and all the name-spaces in the MRO. But, you can actually *shadow* class-variables with instance variables. So, say you had a mix of *both* your original definition and the modified one, then you essentially create a useless class-variable that always gets shadowed — juanpa.arrivillaga, Dec 12 '17 at 00:12

juanpa.arrivillaga · Accepted Answer · 2017-12-12T00:07:11.540

The problem is your class definition. What you've written in Python creates a class variable, perhaps coming from a C# background, one would say it creates a "static attribute". In any event, you need an instance attribute, like this:

In [2]: import copy
   ...:
   ...: class SimState:
   ...:     def __init__(self):
   ...:         self.stateDescriptions = []
   ...:
   ...: def search_recursive(state: SimState, move, recurseDepth):
   ...:     if(recurseDepth > 2):
   ...:         return
   ...:     state.stateDescriptions.append('{0}'.format(move))
   ...:     print('{0}: '.format(recurseDepth) +  ','.join(state.stateDescriptions))
   ...:     for n in range(2):
   ...:         newState = copy.deepcopy(state)
   ...:         search_recursive(newState,n + 1,recurseDepth + 1)
   ...:
   ...: initialState = SimState()
   ...: search_recursive(initialState,0,0)
   ...:
0: 0
1: 0,1
2: 0,1,1
2: 0,1,2
1: 0,2
2: 0,2,1
2: 0,2,2

Also, I'm not sure what you mean by "python manages objects by reference", but Python does not support call-by-reference semantics. Its semantics are similar to Java - except that Python is a pure-OOP language, there are no primitive types, and everything is an object (so, it would be like Java except everything is a reference type). This strategy is technically called call by object sharing

Thanks - I thought declaring something the way I had in a class would create a member variable which is obviously not correct. Updating to using __init__ and assigning at that point has resolved the problem. — Dan James, Dec 12 '17 at 00:12

Recursion behavior in Python vs C# - Strange results

1 Answers1