Passing reference to an object

Question

I am checking whether the specified word can be formed on this boggle board with the canForm method. The board has a graph field which indicates adjacent tiles. I do a DFS and set answer to true if the word can be formed.

I understand why the code as it is below doesn't work: answer is a primitive, its value is copied at every recursion and the initial answer (in the public method) stays false.

If I change boolean answer to Set<String> answer = new HashSet<>() for instance, pass the reference to the set in recursion, eventually add the successfully formed word and test for emptiness in the end, it works.

But why does it not work if I simply declare Boolean answer = new Boolean(false) and pass this container? It passes the reference to the object all right, but it mysteriously changes the reference at assignment answer = true (as seen through the debugger), and the initial answer isn't reset. I don't understand.

public boolean canForm(String word) {

    boolean answer = false;
    int n = M * N;
    char initial = word.charAt(0);

    // for each tile that is the first letter of word
    for (int u = 0; u < n; u++) {
        char c = getLetter(u / N, u % N);
        if (c == initial) {
            boolean[] marked = new boolean[n];
            marked[u] = true;
            canForm(u, word, 1, marked, answer);
        }
    }

    return !answer;
}

private void canForm(int u, String word, int d, boolean[] marked, boolean answer) {

    if (word.length() == d) {
        answer = true;
        return;
    }

    for (int v : graph.adj(u)) {
        char c = getLetter(v / N, v % N);
        if (c == word.charAt(d) && !marked[v]) {
            marked[v] = true;
            canForm(v, word, d + 1, marked, answer);
        }
    }
}

Answer 1

Ah, you're using Java. This matters greatly.

Java is, exclusively, a pass by value language. As such, when you call canForm(int, String, int, boolean[], boolean), you are doing two things:

• You are creating 5 new variables in the scope of the canForm method
• You are initializing them with values from the call site

Altering the values of of the new variables you created will not have any affect on the values of those variables at the call site. Any re-assignments you make will be lost when the method call ends and will have no impact on the values at the call site.

However, in the case of arrays or objects, the "value" being passed is actually a reference to an object. This can be a bit confusing, but it's like the caller and the method each have their own personal key to a shared mailbox. Either could lose their key or replace it with a key to a different mailbox without affecting the other's ability to access the mailbox.

As such, the method can alter the value of the reference (marked = new boolean[]) without altering the caller's reference. However, if the method changes content WITHIN the referenced structure (marked[0] = false) it will be seen by the caller. It's like the method opened the shared mailbox and changed the mail inside. Regardless of which key you use to open it, you'll see the same changed state.

A great analysis: http://javadude.com/articles/passbyvalue.htm

In general:

• If you want to return a value from a method, that should be the return value of the method. This makes the code easier to understand, less likely to have side effects and may make it easier for the compiler to optimize.
• If you want to return two values, create an object to hold both of them (A general purpose type safe container called a "Tuple" is available in many languages and frameworks).
• If you really need to move state between function calls -- and you usually don't -- wrap it with an object to get the equivalent of pass by reference semantics. That's essentially what you're doing when you add your results to a shared Set. Just be aware: programming with side effects, be they shared objects or global state, is defect prone. As you pass a mutable object around, it becomes hard to keep all the potential mechanisms for change in your head. If you can do a job by exclusively through return values, you should try to do so. Some might calls this a "functional [programming] style."
• When you give two methods with different intent the same name, it creates confusion, both for readers and in some cases for the compiler. Be specific. We're in no danger of running out of characters.
• Finally, you may want to read up on tail recursion. Due to that loop, I believe this implementation may be a stack overflow waiting to happen -- just give it a string that's longer that your stack is deep.