Java recursion pass by value/reference

Question

I'm returning to Java after 2 years working in PHP. Sorry if this seem silly:

This is the code (Depth-First Traversal of a graph):

public List<List<Edge>> paths = new ArrayList<>();

public void traverse(Edge edge, List<Edge> currentPath){
    String vertex = graph.getEdgeTarget(edge);
    if(edge!=null) currentPath.add(edge);
    if(vertex=="TARGET_VERTEX"){
        System.out.println(currentPath);  // prints fine

        paths.add(currentPath); // elements are empty at end of reccursion

        if(edge!=null) currentPath.remove(edge);
        return;
    }
    for(Edge e : graph.outgoingEdgesOf(vertex)){
        traverse(e, currentPath);
    }
    if(edge!=null) path.remove(edge);
}

public void search(){
    //graph is initalized, vertices and edges are added

    for(Edge e : graph.outgoingEdgesOf("START_VERTEX")){
        traverse(e, new ArrayList<Edge>());
    }
    System.out.println("############################");
    System.out.println(paths);
    System.out.println(paths.size());
}

Can someone explain why at the end of the recursion paths has empty elements, and how to make it contain the paths I need?
Seems like passing by reference makes me a problem ...

ArrayList has a shallow clone() method, which won't copy the elements (as per JavaDoc).
Do I need to create a temporary variable which will be a manual copying of the currentPath (iterating through the values)?

I'm still a bit confused about passing by value and by reference in Java, which in PHP is easily distinguished by using pass by reference (&variable.)

Edited so I won't get complains about string comparison

Java is *pass by value*. Period. You're also not comparing strings correctly. — Brian Roach, Jul 23 '13 at 17:26
http://stackoverflow.com/questions/40480/is-java-pass-by-reference — assylias, Jul 23 '13 at 17:27

score 1 · Answer 1 · edited May 23 '17 at 11:57

1

The line if(edge!=null) currentPath.remove(edge); removes the element of your List.

This is likely to cause your problem, as currentPath is recursed.

On an unrelated matter, you are comparing String with == instead of using equals, which is bad practice. (See here for more explanations).

edited May 23 '17 at 11:57

Community

1
1

answered Jul 23 '13 at 17:25

Mena

47,782
11
87
106

score 1 · Answer 2 · answered Jul 23 '13 at 17:25

1

These two lines are causing the issue:

      paths.add(currentPath);
      currentPath.remove(edge);

When you add currentPath to paths, it adding the reference of currentPath. In the end, currentPath is empty and hence paths is left with empty references.

To avoid the issue, create a copy of currentPath and add the copy in paths.

Also update the line below:

 if(vertex=="TARGET_VERTEX"){

as

  if("TARGET_VERTEX".equals(vertex)){

to use the proper string equality check and avoid NullPointerException.

If you want to ignore the case whily checking then use equalsIgnoreCase() method.

answered Jul 23 '13 at 17:25

Yogendra Singh

33,927
6
63
73

I still can't get my mind on this pass-by-value/pass-by-reference (I know what each do, but this recursion is a bit strange case to me)... Anyway, as I said, do I need to manually iterate like this (semi-pseudo because of formatting) `List tmp; for(i in currentPath){tmp.add(i)}; paths.add(tmp);` ? As for string checking, I blame PHP and my absence from Java :) – ekstrakt Jul 23 '13 at 17:33
I don't see any major complications in the recursion as related to the passing way, what is the confusion? Is it about printing the variable? – Christian Vielma Jul 23 '13 at 18:12
@ChristianVielma It is about getting a list of all simple paths connecting two vertices. And they are checked in the recursion. – ekstrakt Jul 23 '13 at 18:50
@ekstrakt As I mentioned, when you add `currentPath` to `paths`, it adding the **reference** of currentPath – Yogendra Singh Jul 23 '13 at 21:33

score 1 · Answer 3 · edited May 23 '17 at 12:03

1

You're adding and removing from paths. It seems that it is doing it wrongly, you can try debugging the app.

Java is pass-by-value. What this means is that a method like

public void myMethod(MyObject instance) {...}

receives a copy of the value of the reference to instance. If within the method you did

instance.setField(newValue);

then you are accessing the same object that you passed because the reference has the same value. However, if you did this within the method

instance = new MyObject(newValue);

then the object that was used to call the method will remain unchanged. This happens because you changed the value of the reference in a copy, not in the original

You can see it explained with more detail at javadude.

Finally, you should compare Strings and other objects with .equals method instead of using ==. This answer should help you.

Doing a bird view of your code, I would correct it to this (didn't try): by Create constants for string constants.

//These two lines, minor improvements
public static final String TARGETV= "TARGET_VERTEX";
public static final String STARTV= "START_VERTEX";

Change

if(vertex=="TARGET_VERTEX"){

to

  if(vertex.equals(TARGETV)){

About printing the paths variable, System.out.println will print a String, you're passing an Object (a List of Lists of edges). Each object has a toString() method that is call automatically when the Object is required as String. As stated in the docs, by default:

The toString method for class Object returns a string consisting of the name of the class of which the object is an instance, the at-sign character `@', and the unsigned hexadecimal representation of the hash code of the object.

So instead you could:

Create a new class (that implements internally a List<List<Edge>> and override the toString() method) or you could implement a method like this:

public static String printPath(List<List<Edge>> paths){
   StringBuffer sb = new StringBuffer();
   for(List<Edge> le : paths){
     for(Edge e: le){
         sb.append(le); //or similar method to print edges to String
      }
   }
   return sb.toString();

}

And instead of:

System.out.println(paths);

do this:

System.out.println(printPaths(paths));

edited May 23 '17 at 12:03

Community

1
1

answered Jul 23 '13 at 17:35

Christian Vielma

15,263
12
53
60

Adding/removing is working fine. I just need the current content of the variable (pass it by value). – ekstrakt Jul 23 '13 at 17:41
Ah that's a different thing: you have to implement a toString method or print it on your own. System.out.prinln(paths) is going to print the variable's value. – Christian Vielma Jul 23 '13 at 17:44
@SotiriosDelimanolis and that's what I said. It is passed by value, but Objects variables are in fact references. So if you pass a reference by value, when you modify the content of that reference is as in fact you've been passed the real Object by reference. – Christian Vielma Jul 23 '13 at 17:46
@SotiriosDelimanolis corrected redaction to avoid further confusion. – Christian Vielma Jul 23 '13 at 17:52
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/34005/discussion-between-christian-vielma-and-sotirios-delimanolis) – Christian Vielma Jul 23 '13 at 17:57
@SotiriosDelimanolis done man, removed it. I hope it's more clear and not misleading for Java newbies. – Christian Vielma Jul 23 '13 at 17:58
@ChristianVielma I added a description to explain it in more detail. – Sotirios Delimanolis Jul 23 '13 at 18:03
I'm overriding the `.toString()` method, no issues there. (I'm not a Java n00b, I have worked 3 years with it, it's just my memory is a bit confused by 2 years of PHP). – ekstrakt Jul 23 '13 at 18:08
@SotiriosDelimanolis great! ekstrakt no pun intended! Did it work? – Christian Vielma Jul 23 '13 at 18:10
I haven't changed anything, the `.toString()` method is overriden before I asked the question. But nevermind, I'm creating a local temporary variable, and copying the contents of path in it, than add that variable to the main List. I just wanted to know why is this happening, and will manual copy be the only solution. Thanks. – ekstrakt Jul 23 '13 at 18:48

score 0 · Answer 4 · answered Jul 25 '13 at 21:54

The first thing you need to know is that objects are not values in Java. The only types in Java are primitive types and reference types, so the only values in Java are primitives and references. A "reference" is a pointer to an Object. paths, currentPath, edge, etc. in your code are all references. The elements of paths and of currentPath are also references. When you assign or pass a reference, you get another reference that points to the same object. A new object can basically only be created when you do new ....

So from this it should become more apparent what is going on. The only place where a list of edges is ever created in your code is in the search() function, when it calls the traverse() function. The traverse() function does not contain any object creation expressions. So in all the recursion and all that, it is working with and modifying the same list object. Each call to traverse() adds and then removes an element. So at the end of the recursion, there will be no elements in the list. This is the same list whose reference you added to paths, so of course you see references to empty lists in paths at the end.

You said you worked in PHP. In PHP5, objects work in the same way -- objects are not values in PHP, and they are only manipulated through pointers to objects. However, arrays in PHP (which are not objects) are different; arrays in PHP are values, and so when assigned or passed, the array is copied.

Java recursion pass by value/reference

4 Answers4