Рекурсия реверсирует SingleLinkedList и печатает как String - PullRequest
Новая
       12

Рекурсия реверсирует SingleLinkedList и печатает как String

1 голос
/ 12 апреля 2020

Мне было дано задание добавить метод, обращенный к SingleLinkedList, предпочтительно с использованием рекурсии. 

   public String reversed() {
     StringBuilder b = new StringBuilder();
     reversed(first, b);
     return b.toString();
}
    private void reversed(Node<E> n, StringBuilder b) {
       if (n != null) {
         reversed(n.next, b);
         b.append(n.element);
         b.append(’\n’);
      }
}

Кажется, что работает очень хорошо, когда я тестирую в eclipse.

Однако я не уверен, что понимаю 100% почему.

Вот как я думаю. Давайте представим, что у нас есть SingleLinkedList с 5 узлами, и мы вставляем первый узел в приватный метод, чтобы изменить его.

  1. Поскольку n не равно нулю, это первый узел. Он введет оператор if.
  2. Он вызовет сам себя, но теперь с Node second он не равен нулю, так как будет повторяться ....
  3. Теперь он достигает Node 5, он вызывает сам по себе, но тогда он будет вызывать обратное (шесть, б), поскольку узел Node шесть существует и является нулевым, он не будет работать. Поэтому он перемещается в строку "b.append (n.element);" Однако. Теперь он запоминает, где он начался, и добавляет «first.element»; после этого он добавит новый ряд.

Что объясняет логику c, что она будет в дальнейшем добавлять second.element; Может кто-нибудь объяснить, как я должен думать, чтобы понять, что теперь он будет добавлять второй элемент?

Заранее спасибо, думаю, что мне действительно нужно понять это при полной рекурсии в java

1 Ответ

0 голосов
/ 13 апреля 2020

Каждый вызов метода сохраняет свое собственное состояние. Как только вы доберетесь до узла 6, в стеке будет 5 вызовов, ожидающих окончания reversed(n.next, b) до sh. Каждый метод может продолжаться только после завершения вызова reversed в стеке над ним.

В этом примере вы выполняете последним в качестве первого, т.е. у вас есть нехвостовая рекурсивная функция (рекурсивная вызов происходит до того, как вы выполните действие этого метода).

Представьте себе, что каждый раз, когда вы получаете reversed, вы заменяете вызов этого метода кодом, который он будет выполнять. Помните, что все вызовы происходят последовательно (есть только один поток, ничего не может происходить параллельно). Вы получите что-то похожее на это: 

if (n0 != null) {
    Node<E> n1 = n0.next;
    if (n1 != null) {
        Node<E> n2 = n1.next;
        if (n2 != null) {
            Node<E> n3 = n2.next;
            if (n3 != null) {
                Node<E> n4 = n3.next;
                if (n4 != null) {
                    Node<E> n5 = n4.next;
                    if (n5 != null) {
                        // would be null so nothing happens
                    }
                    b.append(n4.element);
                    b.append('\n');
                }
                b.append(n3.element);
                b.append('\n');
            }
            b.append(n2.element);
            b.append('\n');
        }
        b.append(n1.element);
        b.append('\n');
    }
    b.append(n0.element);
    b.append('\n');
}

Вы можете увидеть, как этот код становится довольно трудно читать, когда число элементов увеличивается. Когда мы не знаем точно, сколько будет длиться список, этот подход ломается ... вы не захотите делать это 10, 100 или, возможно, тысячи раз!

Именно поэтому рекурсия так полезно для таких приложений, как это. Мы можем повторно использовать интересную логику c, не зная длины списка, и можем значительно сократить дублирующийся код.

Просто имейте в виду, что рекурсия происходит с затратами памяти. Каждый раз, когда вы вводите рекурсивный метод, вы добавляете состояние в стек. После того, как вы загрузите память на своем компьютере, вам придется начать искать нерекурсивные способы выполнения этой работы.

...