java - 递归方法中ArrayList的状态

Question

我有一个像这样的递归方法：

class MyClass {
ArrayList<ArrayList<MyNode> allSeriesOfNodes = new ArrayList<ArrayList<MyNode>();

public void myMethod(MyNode currNode, ArrayList<MyNode> nodes) {
    // make sure currNode and nodes aren't null, blah....
    nodes.add(currNode);
    for(MyNode n: otherNodeList) {
        for(listItem in n.getList()) {
            if(...) {
                myMethod(n, nodes);
        }
    }
if(currNode is a leaf and nodes is > 1) {
    allSeriesOfNodes.add(nodes);
}

调试它时，我注意到当弹出一个堆栈帧并且恢复上一个堆栈帧时，尽管它弹出了，节点列表仍然具有currNode的值。

就像currNode一样，nodeslist是一个局部变量，递归应该记住每个堆栈帧的nodelist的状态。返回上一个堆栈框架，为什么不显示节点列表A而不是A，B（弹出myMethod（B，nodes））。

Answer 1

序幕

编辑：与问题所有者聊天后，答案仍然不清楚，因此我认为有必要更好地阐明答案。

的确，Java中的所有内容都是按值传递的，也就是说，堆栈框架上的值无法更改。要注意的是，将对象作为参数传递给方法时，引用（内存地址）作为值传递给函数。由于引用只是一个值，因此无法更改引用本身，但这当然并不意味着您不能更改正在引用的内存中对象的实例。

对于初学者甚至是经验丰富的C / C ++程序员，这可能有些令人困惑。在C / C ++中，经典指针可以更改与该指针关联的引用，并且可以更改引用所指向的对象的值。因此，我声明Java使用了我所谓的准指针，准含义（“是，但不是”），然后是指针，它是经典的C指针。

考虑以下不可变类的示例（对象不可变性很重要，可能会使您感到困惑）。非不可变基本上只是意味着对象的状态可以改变。

public static void main(String[] args) {
    NonImmutable ni = new NonImmutable(0);
    mystery1(ni);
    System.out.println(ni.value);
}

public static void mystery1(NonImmutable ni) {
    ni = new NonImmutable(7);
    System.out.println(ni.value);
}

public static class NonImmutable {
    public int value;

    public NonImmutable(int value) {
        this.value =  value;
    }
}

在上面的代码片段中。您会注意到输出是。

7
0

现在让我们假设，当调用应用程序时，main方法在堆上的地址0x123456处创建了NonImmutable对象。当我们调用mystery1时，它看起来确实像这样

mystery1(0x123456) //passing the reference to Non Immutable instance as a value!

因此在函数内部我们有ni = 0x123456，但请记住，这只是引用的一个值，而不是经典的C指针。因此，在mystery1内部，我们先在堆上的另一个内存地址0x123abc上创建另一个Non Immutable对象，然后将其设置为参数ni的值，以使ni = 0x123abc。现在，让我们停下来思考一下。由于在Java中一切都是传递值，因此设置ni = 0x123abc并没有什么不同，然后将其设置为该值（如果它是原始int数据类型）。因此，传入的对象的值不会更改，因为内存地址只是一个值，与某些int，double，float，boolean等的值没有不同。

现在考虑下一个示例...

public static void main(String[] args) {
    NonImmutable ni = new NonImmutable(0);
    mystery2(ni);
    System.out.println(ni.value);
}

public static void mystery2(NonImmutable ni) {
    ni.value = 7;
    System.out.println(ni.value);
}

public static class NonImmutable {
    public int value;

    public NonImmutable(int value) {
        this.value =  value;
    }
}

您会注意到上面示例的输出将是。

7
7

我们将做与第一个示例相同的假设，即，初始的Non Immutable对象是在堆上的内存地址0x123456上初始化的。现在，执行神秘2时，会发生完全不同的事情。当执行ni.value时，我们实际上是在执行以下内容

(0x123456).value = 7 // Set the value of instance variable Non Immutable object at memory address 0x123456 to 7

上面的代码确实会更改对象的内部状态。因此，当我们从mystery2返回时，我们具有指向将打印7的同一对象的指针。

既然我们了解了不可变对象的工作原理，您可能会注意到在传递对象时有一些不寻常的情况，但是上述准指针似乎并不一致。好吧，它实际上是一致的，但是面向对象语言中存在另一种对象，可以使您产生不一致的错觉，但不要被愚弄。 Java中还有一些称为不可变对象的对象，例如此处指定的String对象（http://docs.oracle.com/javase/7/docs/api/java/lang/String.html）。

不可变对象只是意味着不能更改对象的内部状态。对，那是正确的。每次您做以下事情

String foo = "foo";
String moo = foo + " bar";

moo没有引用foo，因为String foo是不可变的，因此当执行foo +“ bar”时，连接操作会在堆上创建一个全新的String对象。这意味着，当传递String对象（或与此相关的任何不可变对象）作为方法的参数时，您不能更改不可变对象的状态。因此，您对Immutable对象执行的任何操作实际上都会在堆上创建新的Object，因此将像上面的mystery1示例中那样引用新的堆对象。

这是传递不可变对象的递归示例。

public static void main(String[] args) {
    foo(4, "");
}

public static void foo(int i, String bar) {
    if(i==0)
        return;

    bar += Integer.toString(i);
    foo(i-1, bar);
    System.out.println(bar);
}

您会注意到输出看起来像这样

4321
432
43
4

请注意，我们没有收到像您期望的4321那样的东西。这是因为在每个递归调用中，都会在堆上创建一个新字符串，以表示由串联创建的新字符串。

希望这可以消除发问者的困惑，这对其他人有帮助。

另一个很好的参考
http://www.yoda.arachsys.com/java/passing.html。

对于眼前的问题

因为当您通过java中函数的参数传递变量时，它是按值传递。在对我的方法的首次调用中，您要传入一个数组列表对象，该对象与整个递归算法中的指针相同。如果希望节点成为堆栈框架上的局部变量，则必须创建一个局部变量，即在方法签名中未指定为参数

这是一个教程，解释了如何通过复制值引用传递Java对象。
http://www.javaworld.com/article/2077424/learn-java/does-java-pass-by-reference-or-pass-by-value.html

是的，您想使用什么术语。事实是，它是相同的指针。

class MyClass {
ArrayList<ArrayList<MyNode> allSeriesOfNodes = new ArrayList<ArrayList<MyNode>();

public void myMethod(MyNode currNode) {
    List<MyNode> nodes = new ArrayList<MyNode>();  //nodes list as a local variable
    // make sure currNode and nodes aren't null, blah....
    nodes.add(currNode);
    for(MyNode n: otherNodeList) {
        for(listItem in n.getList()) {
            if(...) {
                myMethod(n);
        }
    }

    if(currNode is a leaf and nodes is > 1) {
        allSeriesOfNodes.add(nodes);
    }
}