Java Recursion - альтернатива передаче по ссылке:

Question

Я переношу с C на Java, и у меня возникают трудности с рекурсией, особенно потому, что в Java вы не можете передавать аргумент по ссылке.

Что я ищу, это не решение/трюк, чтобы заставить Java передать аргумент по ссылке, но рекомендуемый способ решить такую ​​проблему на Java.

Давайте рассмотрим вставку рекурсивного узла в бинарном дереве:

void nodeInsert(Node n, int a) { 
    if (n == null) 
     n = new Node(a); 
... 
} 

В С, к концу выполнения, узел n в дереве будет указывать на вновь созданный узел. В Java, однако, n по-прежнему будет null (поскольку n передается по значению).

Что такое предлагаемый подход Java для таких проблем? Некоторые подходы я уже пробовали:

• Использование статического объекта для отслеживания родителя (вопрос усложняет при использовании дженериков).
• Передача родительского узла как часть функции. Он работает, но немного усложняет код и не выглядит хорошим решением.
• Создание дополнительного элемента, указывающего на родительский узел, но это не является хорошим решением, так как оно увеличивает пространство, необходимое для O (n);

Любые советы приветствуются.

Answer 1

Вы можете передать объект держателя, который в свою очередь ссылается на свой новый Node объект

void nodeInsert(AtomicReference<Node> r, int a) { 
    if (r.get() == null) 
     r.set(new Node(a)); 
... 
} 

Или вы можете передать массив с пространством для одного элемента.

Answer 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/ научит вас правильно.

Answer 3

Я предлагаю следующие решения:

• Реализовать метод в классе Node, который добавляет дочерний узел. Это использует OO-возможность инкапсулировать данные и функциональные возможности вместе в классе.

• Изменить nodeInsert, чтобы вернуть новый узел и добавить его в родительский элемент в вызывающем устройстве (также упоминается в комментариях). Ответственность nodeInsert заключается в создании узла. Это четкая ответственность, и сигнатура метода показывает, каков результат метода. Если создание не превышает new Node(), для него не может быть отдельного метода.

Answer 4

Общим способом реализации является поддержание связей узлов внутри самого узла. Довольно много примеров можно найти в реализациях различных структур данных JDK.Таким образом, узел является контейнером для значения и содержит ссылки на другие узлы, в зависимости от структуры данных.

Если вам нужно> детей-родительские отношения между узлами, класс 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 без сжатых указателей)

Answer 5

После нескольких месяцев публикации этого вопроса я понял еще одно решение, которое, по сути, уже рассматривается в шаблонах java-дизайна, но не упомянуто здесь: Null Object Pattern. Недостатком является то, что каждый нуль занимает память (в некоторых случаях, как и крупные деревья Красно-Черных, это может стать значительным).