CODEWITHSUNDEEP
java
Viper344
Viper344

Reputation:

Recursive Linked Lists in Java

I am working on an assignment that has me writing a java program to print out in reverse order the data contained in a linked list using recursion. So far this is what I have, it works but only on the final element in the list IE. it stops once it prints the last element.

public String reverse(IntNode head){
        String result = "";
        if(head.getLink() == null){
            result += head.getData();
            return result;
        }

        else if(head.getLink().getLink() == null){
            result += head.getLink().getData();
            head.removeNodeAfter();
            return result;
        }

        else{
            return reverse(head.getLink());
        }
    }

How would I get it to keep going through the list backwards up the recursive tree?

Upvotes: 5

Views: 1232

Answers (3)

Todd Lehman
Todd Lehman

Reputation: 2930

As others have pointed out, your solution is more complicated than it needs to be.

First, note that you don't need to (and probably don't want to) remove any items from the list in order to traverse it.

Second, rather than checking if the current node's link is null, you can actually check if the current link itself is null (nothing wrong with that so long as you don't attempt to dereference it). This simplifies the logic.

public String reverse(IntNode head) {
    if (head == null)
        return "";
    else
        return reverse(head.getLink()) + head.getData();
}

Or you could even write it like this:

public String reverse(IntNode head) {
    return (head == null)? "" : reverse(head.getLink()) + head.getData();
}

Upvotes: 3

seand
seand

Reputation: 478

This code is more complicated than it needs to be. In this case the recursion can be broken down into 2 cases (or 2 execution paths the function might have):

  1. Recursive case: this path calls itself so that recursion can start (or continue)
  2. Base case: this path ends the recursion by returning without calling itself

Your code has 2 base cases, and it only needs 1. Think about all the different inputs you can call the function with:

  1. head is null

  2. head is an IntNode:

    a. head.getLink() returns null

    b. head.getLink() returns an IntNode:

    1. head.getLink().getLink() returns null

    2. head.getLink().getLink() returns an IntNode

You'll start to notice a pattern; once it's simplified there are really only 2 possible inputs:

  1. head is null
  2. head is an IntNode

If head is an IntNode, the function can call itself with head.getLink() (the recursive case) and it can be only those same 2 inputs, and this continues until head becomes null (the base case).

To answer your actual question, it only returns the last element's value because in the recursive case, you're not actually prepending the value of the current IntNode (i.e. head.getData()); you're just returning the result of the next reverse() call, which means it will recurse until it gets to the last element, and return just that element's value.

Upvotes: 2

mindvirus
mindvirus

Reputation: 5246

When thinking about recursion, it's a good strategy to build up from the ground, until you hit interesting cases. At each step, try to reuse previous cases.

Q1. What is the reverse of an empty list? []

A1. An empty list. []

Q2. What is the reverse of a list with a single element? [ 1 ]

A2. The same list. [ 1 ]

Q3. What is the reverse of a list with two elements? [ 1 2 ]

A3. The first element, appended to the second element. [ 2 1 ] (Starting to get interesting)

Q4. What is the reverse of a list with three elements? [ 1 2 3 ]

A4. The first element, appended to the reverse of the list of the remaining elements. [ 3 2 ] + [ 1 ] = [ 3 2 1]

Now the pattern should start to be clear: the reverse of a list of N elements is the reverse of the last N - 1 elements with the first element appended).

What is our base case? From the above, it appears having a list of 1 or 0 elements. Look closer though, applying our pattern to a list of length 1, we see that [ 1 ] reversed is [] with the first element appended, ie [] + [ 1 ]. So really, our base case is just the empty list.

Upvotes: 2

Related Questions