提问人： 提问时间：10/28/2016 最后编辑：Lahiru Ashan 更新时间：5/17/2017 访问量：1610
Java 递归 - 传递引用的替代方法：
Java Recursion - Alternative to passing-by-reference:
问：
我正在从 C 迁移到 Java，并且在递归方面遇到了困难，特别是因为在 Java 中，您无法通过引用传递参数。
我正在寻找的不是强制 Java 通过引用传递参数的解决方案/技巧，而是在 Java 中解决此类问题的推荐方法。
让我们以二叉树中的递归节点插入为例：
void nodeInsert(Node n, int a) {
if (n == null)
n = new Node(a);
...
}
在 C 语言中，在执行结束时，树中的节点将指向新创建的节点。然而，在 Java 中，仍然是（因为 n 是按值传递的）。nnnull
对于此类问题，建议采用的 Java 方法是什么？ 我已经尝试过的一些方法：
- 使用静态对象来跟踪父对象（使用泛型时问题会变得复杂）。
- 将父节点作为函数的一部分传递。它有效，但使代码有点复杂，看起来不是一个好的解决方案。
- 创建一个指向父节点的附加成员，但这不是一个好的解决方案，因为它增加了 O（n） 所需的空间;
欢迎任何建议。
答：
0赞
Roger Lindsjö
10/28/2016
#1
您可以传递一个持有者对象，该对象反过来引用您的新对象Node
void nodeInsert(AtomicReference<Node> r, int a) {
if (r.get() == null)
r.set(new Node(a));
...
}
或者，您可以传递一个包含一个元素空间的数组。
评论
0赞
10/28/2016
有趣的方法。我会尝试的。
0赞
user140547
10/28/2016
@Nelsao 请注意，AtomicReference 是一种并发数据结构，可能会影响性能。
1赞
paulsm4
10/29/2016
传递数组或列表，以及被调用方修改该容器中的元素，是“out 参数”的常用用语。“AtomicReference”（不是“AtomicReverence”;)）可能是这个问题的一个糟糕的选择。但真正的重点是：“如果你不需要一个”输出参数“......那就不要试图捏造一个”。恕我直言......
3赞
DragNa
10/28/2016
#2
在 Java 中，我们不使用引用变量，而是使用返回值并将其分配给必须更改的变量。
Node nodeInsert(Node n, int a) {
if (n == null){
n = new Node(a);
return n;
}
else
{
....
return nodeInsert(n,a); //this is how a recursion is done.
....
}
}
如果你需要更多关于递归的信息，http://www.toves.org/books/java/ch18-recurex/ 会教你正确的。
1赞
mm759
10/28/2016
#3
我提出以下解决方案：
在类中实现添加子节点的方法。这利用了 OO 的可能性将数据和功能一起封装在一个类中。
Node更改以返回新节点并将其添加到调用方中的父节点（在注释中也提到）。的职责是创建节点。这是一个明确的责任，方法签名显示方法的结果是什么。如果创建不超过，则可能不值得为其使用单独的方法。
nodeInsertnodeInsertnew Node()
2赞
Gerald Mücke
10/28/2016
#4
一种常见的实现方式是在节点本身内部维护节点关系。在各种 JDK 数据结构的实现中可以找到相当多的示例。因此，Node 是值的容器，并包含对其他节点的引用，具体取决于数据结构。
如果需要节点之间的子>父关系，则 Node 类将如下所示
class Node<T> {
T value;
Node parent;
}
在插入的情况下，创建一个新节点，将父引用设置为原始节点，然后返回新节点作为结果（这是可选的，但并不少见，因此调用具有新子节点的句柄）
Node<T> insert(Node<T> parent, T value) {
Node<T> child = new Node<>();
child.value = value;
child.parent = parent;
return child;
}
是的，这会增加每个节点 4 个字节的轻微开销（或 8 个字节，在没有压缩指针的 64 位 JVM 上）
0赞
user6412203
5/17/2017
#5
在发布这个问题几个月后，我意识到了另一个解决方案，事实上，这个解决方案已经在 java 设计模式中考虑过了，但这里没有提到：空对象模式。 缺点是每个 null 都会占用内存（在某些情况下，例如大型红黑树，这可能会变得很重要）。
评论
Node nodeInsert(Node n, int a)insertNode()