Keeping instances of variables in recursion

Question

I'm trying to make a program for find all the Euler Paths in a graph. For doing this, I'm using a code adapted from this: http://www.sanfoundry.com/java-program-implement-euler-circuit-problem/

What I do: I modified a recursive function printEulerUtil() (below) for test and find (method isValidNextEdge) the possibles Euler paths. But, my recursive method doesn't stores the variable int[][] localAdjacencyMatrix (it's like a global variable, i can't understand that), which means that when the recursion returns (for example, after find the first Euler path in a deep first search), my variable is the same of the last recursive call (like I said, a global variable behaviour), not storing the values of the "original" call before in the program (the contexts before the first recursion call).

What I'm doing wrong? All the context is not saved when recursion occurs, after all?

Here is a piece of the code (commented):

// in the main call, variable vertex and localAdjacencyMatrix are defined in the constructor.
public void printEulerTourUtil(int vertex, int[][] localAdjacencyMatrix) {

        ArrayList<Integer> destinationVertexes = new ArrayList<>();
        int destination = 1;
        // print the actual vertex
        System.out.println("V: " + vertex);

        for (destination = 1; destination <= numberOfNodes; destination++) {
            // test all possibles destinations
            if (localAdjacencyMatrix[vertex][destination] == 1 && isValidNextEdge(vertex, destination, localAdjacencyMatrix)) {
                // insert these destinations in a list of next vertex for recursion
                destinationVertexes.add(destination);
                System.out.println(destination + " ");
            }
        }

        // make a recursion for every vertex destination in the list.
        for (int i = 0; i < destinationVertexes.size(); i++){
            destination = destinationVertexes.get(i);
            // go to the next vertex in the graph
            System.out.println("-> source : " + vertex + " destination " + destination);

            // localAdjacencyMatrix isn't working. it's like a global variable, so my recursion fails
            removeEdge(vertex, destination, localAdjacencyMatrix);
            printEulerTourUtil(destination, localAdjacencyMatrix);
        }

Sorry any english mistake and any help will be very useful! Thank you!

Answer 1

Arrays as reference types (unlike an int which is a primitive). So each time you pass the array to the method via recursion you are just passing a reference to the same array object. Basically, you don't need to pass the reference since all method invocations are getting references to the array field.

If you need a new array instance per invocation, you need to create a new array to pass in.

Answer 2

The localAdjacencyMatrix array is not local at all. It is passed from the outside to the first call to printEulerTourUtil, and later it is passed to each recursive call. Therefore, each recursive call sees and modifies the same instance of this array.

On the other hand, your destinationVertexes variable is local. It is defined within the scope of the printEulerTourUtil method, so each recursive execution of this method instantiates a new instance of that list.

I'm not sure what you need, but if your logic requires that localAdjacencyMatrix be local, you should declare and instantiate it within the printEulerTourUtil method.

Answer 3

Since the array localAdjacencyMatrix is passed by reference in Java, you need to clone it at the top of your method first if you don't want to modify the original array. Note, however, that the Java clone() method won't work by itself on a multidimensional array. See how to clone multidimensional arrays.