递归方法中 ArrayList 的状态 [英] State of an ArrayList in a recursive method
问题描述
我有一个像这样的递归方法:
I have a recursive method like so:
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 的值，尽管它弹出了.
Debugging it I noticed when a stack frame pops and the previous stackframe resumes, the nodes list still has the value of currNode although it popped off.
nodeslist 和 currNode 一样是一个局部变量，递归应该记住每个栈帧的 nodelist 状态.回到之前的stackframe，为什么不是nodelist A 而不是A, B (myMethod(B, nodes) was popped) .
nodeslist is a local variable just like currNode, and the recursion should remember the state of nodelist per stack frame. Returning to the previous stackframe, why isn't nodelist A instead of A, B (myMethod(B, nodes) was popped) .
推荐答案
序幕
和题主聊过之后，答案还是不明确，所以我认为有必要更好地阐明答案.
After chat with question owner, the answer was still not clear, so I believe it is necessary to articulate the answer better.
确实，Java 中的一切都是传值，也就是说，堆栈帧上的值无法更改.问题在于，当将对象作为参数传递给方法时，引用(内存地址)作为值传递给函数.由于引用只是一个值，因此无法更改引用本身，但这当然并不意味着您不能更改正在被引用的内存中对象的实例.
It is true that everything in Java is pass-by-value, that is, the values that are on the stack frame can not be changed. The catch is that when passing an object as a parameter to a method, the reference (memory address) is passed as the value to the function. Since the reference is just a value, it is not possible to change the reference itself, but that of course does not mean that you can not change the instance of the object in memory that is being referenced.
这对于初学者甚至是有经验的 C/C++ 程序员来说可能有些令人困惑.C/C++ 中的经典指针可以更改与指针关联的引用，并且您可以更改引用指向的对象的值.因此，我声明 Java 使用我所谓的准指针，准意思(它是，但它不是")，然后是指针，它是经典的 C 指针.
This can be some what confusing for beginning programmers and even experienced C/C++ programmers. Classic pointers in C/C++ it is possible to change the reference associated with the pointer, and you can change the value of the object the reference is pointing to. It is therefore, that I declare that Java uses what I call quasi-pointers, quasi meaning ("It is, but it is not") and then pointer, which is the classic C pointer.
考虑以下 Non Immutable 类的示例(对象不变性很重要，但可能会让您感到困惑).Non Immutable 基本上只是意味着对象的状态可以改变.
Consider the following example of a Non Immutable class (object immutability is important, and could confuse you). Non Immutable basically just means that the state of the object can change.
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;
}
}
在上面的代码片段中.你会注意到输出是.
In the above code snippet. you will notice the output is.
7
0
现在让我们假设，当我们调用应用程序时，main 方法在地址 0x123456 的堆上创建了一个 NonImmutable 对象.当我们调用mystery1时，它真的是这样的
Now let us suppose that when we invoke the application that the main method creates a NonImmutable object on the heap at address 0x123456. When we invoke mystery1, it really looks like this
mystery1(0x123456) //passing the reference to Non Immutable instance as a value!
所以在函数内部我们有 ni = 0x123456，但请记住它只是引用的值，而不是经典的 C 指针.因此，在mystery1 中，我们先在堆上的另一个内存地址0x123abc 处创建另一个非不可变对象，然后将其设置为参数ni 的值，从而使ni = 0x123abc.现在，让我们停下来想一想.由于在 Java 中一切都是传值，因此设置 ni=0x123abc 与将其设置为该值(如果它是原始 int 数据类型)没有什么不同.因此传入的对象的值不会改变，因为内存地址只是一个值，与某些 int、double、float、boolean 等的值没有区别.
so inside the function we have ni = 0x123456, but remember it's just a value to the reference, not a classic C pointer. So inside mystery1, we precede to create another Non Immutable object on the heap at another memory address, 0x123abc, which we then set to the value of the parameter ni, so that we have ni = 0x123abc. Now, let's pause and think about this. Since in java everything is pass-by-value, therefore setting ni=0x123abc is no different then setting it to that value if it were a primitive int data type. Hence the value of the object is not changed that was passed in, because the memory address is just a value, which is no different then the value of some int, double, float, boolean, etc.
现在考虑下一个例子...
Now consider the next example...
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;
}
}
您会注意到上面示例的输出是.
You will notice the output of the sample above will be.
7
7
我们将做出与第一个示例相同的假设，即初始非不可变对象在内存地址 0x123456 的堆上进行初始化.现在，当执行mystery2 时，会发生一些完全不同的事情.当执行 ni.value 时，我们实际上是在执行下面的
We will make the same assumptions as the first example, that is, the initial Non Immutable object is initialize on the heap at memory address 0x123456. Now, when executing mystery2, something quite different happens. When executing the ni.value we are actually executing the below
(0x123456).value = 7 // Set the value of instance variable Non Immutable object at memory address 0x123456 to 7
上面的代码确实会改变对象的内部状态.因此，当我们从mystery2 返回时，我们有指向将打印7 的同一个对象的指针.
The above code will indeed change the internal state of the object. Therefore, when we return from mystery2 we have the pointer to the same object that will print a 7.
现在我们了解了 Immutable 对象的工作原理，您可能会注意到在传递 Objects 时有一些不寻常的情况，但是上面的 准指针 似乎并不一致.嗯，它实际上是一致的，但是在面向对象语言中有一种不同类型的对象可以让您产生不一致的错觉，但不要被愚弄.Java 中也有对象称为不可变对象，例如此处指定的 String 对象(http://docs.oracle.com/javase/7/docs/api/java/lang/String.html).
Now that we understand how Immutable objects work, you may notice there are some unusual cases when Objects are passed, but the above quasi-pointer does not seem to be consistent. Well, it is actually consistent, but there is a different kind of object in Object Oriented Languages that can throw you off to give the illusion of inconsistency, but do not be fooled. There are also objects in Java called Immutable Objects such as the String object specified here (http://docs.oracle.com/javase/7/docs/api/java/lang/String.html).
不可变对象仅仅意味着对象的内部状态不能改变.对，那是正确的.每次你做如下事情
An Immutable Object simply just means that the internal state of the object can not be changed. Yes, that is correct. Every time you do something as below
String foo = "foo";
String moo = foo + " bar";
moo 没有引用 foo，因为字符串 foo 是不可变的，因此当执行 foo + "bar" 时，连接操作在堆上创建了一个全新的 String 对象.这意味着在将 String 对象(或任何与此相关的任何 Immutable 对象)作为参数传递给方法时，您不能更改 Immutable 对象的状态.因此，您对 Immutable 对象执行的任何操作实际上都会在堆上创建新对象，因此将像上面的神秘 1 示例一样引用新的堆对象.
moo is not referencing foo, because the String foo is immutable, and therefore the concatenate operation created a whole new String object on the heap when performing foo + " bar". This implies that when passing the String object (or any Immutable object for that matter), as a parameter to a method, you can not alter the state of the Immutable object. Therefore any operations you perform on the Immutable object will actually be creating new Objects on the heap, and will thus be referencing the new heap objects as in mystery1 example above.
这是传递不可变对象的递归示例.
Here is a recursive example of Immutable objects being passed.
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);
}
你会注意到输出看起来像这样
You will notice the output looks something like this
4321
432
43
4
请注意，我们不会得到您可能期望的四次 4321 的结果.这是因为在每次递归调用中，都会在堆上创建一个新字符串来表示由串联创建的新字符串.
Notice that we don't get something like you might expect 4321 four times. This is because in each recursive call, a new string was created on the heap to represent the new string that was created by the concatenation.
希望这能消除提问者的任何困惑，这对其他人也有帮助.
Hopefully that clears up any confusions that the questioner had, and this can be helpful for others.
另一个很好的参考http://www.yoda.arachsys.com/java/passing.html.
手头的问题
因为在java中通过函数的参数传递变量时，是按值传递的.在您第一次调用我的方法时，您传入了一个数组列表对象，该对象与整个递归算法中的指针相同.如果你想让节点成为栈帧上的局部变量，你就必须创建一个局部变量，即在方法签名中不指定为参数
Because when you pass variables through parameters of functions in java, it is a pass by value. In your first call to my method, you are passing in an array list object which is the same pointer through out your entire recursive algorithm. If you want nodes to be a local variable on the stack frame you will have to create a local variable, that is, not specified as a parameter in the method signature
这是一个教程，解释了如何通过复制的值引用传递 java 对象.http://www.javaworld.com/article/2077424/learn-java/does-java-pass-by-reference-or-pass-by-value.html
Here is a tutorial that explains how java objects are passed by copied value reference. http://www.javaworld.com/article/2077424/learn-java/does-java-pass-by-reference-or-pass-by-value.html
是的，您想使用什么术语.事实是它是同一个指针.
yea what ever terminology you want to use. The fact is that it's the same pointer.
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);
}
}
这篇关于递归方法中 ArrayList 的状态的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
