Recursion reverse a SingleLinkedList and print as a String

user_11164559 0
Viewed 40

I was given the task to add a method reversed to a SingleLinkedList using recursion preferably.

   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’);
      }
}

Seems to work very well when I test in eclipse.

However, I am not sure if I understand 100% why.

This is how I think. Let us imagine we have SingleLinkedList with 5 Nodes and we put in the first Node in the private method to reverse it.

  1. Since n isnt null, its the first node. It will enter the if statement.
  2. It will call on itself, but now with Node second, its not null since it will repeat....
  3. Now it reaches Node 5, it calls itself, but then it will call on reversed (six,b) since Node six dosent exist and is null, it will not work. Therefore it moves to the row "b.append(n.element);" however. It now remembers where it started and appends "first.element"; after that it will append a new row.

What exaplins the logic that it will hereafter append second.element; Can someone explain how I should think to understand that it will now append the second element?

Thanks in advance, think I really need to understand this to under recursion fully in java

singly-linked-list recursion java
1 Answers

Each method call keeps its own state. Once you get to node 6, there will be 5 calls on the stack waiting for reversed(n.next, b) to finish. Each method can only continue after the call to reversed on the stack above it finishes.

In this example you have last in as the first to act, i.e. you have a non-tail recursive function (the recursive call is happening before you perform the action of that method).

Imagine if every time you got to reversed you replaced that method call with the code it would execute. Remember all the calls happens serially (there is only one thread, nothing can happen in parallel). You'd get something that looks like this:

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');
}

You can see how this code gets pretty hard to read once the number of elements goes up. When we don't know exactly how long the list will be this approach breaks down... you wouldn't want to do this 10, 100, or possibly thousands of times!

This is exactly why recursion is so useful for applications like this. We are able to re-use the interesting logic without having to know the length of the list, and are able to reduce duplicated code significantly.

Just keep in mind that recursion comes at a memory cost. Each time you enter the recursive method you add state to the stack. Once you cap out the memory on your machine you'll have to begin looking at non recursive ways of performing this work.

user_32805380
Related