Help with backward recursion and LinkedList in Java

Question

/**
     * Converts linked list into a sentence (a single string representation).
     * Each word pair is separated by a space. A period (".") is appended after
     * the last word. The last link represents the first word in the sentence
     * (and vice versa). The partialResult is the partial string constructed
     * from earlier links. This partialResult is initially an empty string. 
     */
    public String getReversedSentence(String partialResult) {
        if (next==null) {
            partialResult+=this.word;
            return partialResult + ".";
        }
        else{
            partialResult=next.getReversedSentence(partialResult) + this.word;
            return partialResult;
            }
    }

Everything is working fine, except for the period (and the spaces, but Im not worrying about that yet). I cant get the period to be placed properly.

Here's the test it's failing:

public void testGetReversedSentence() {
        LinkedList tail = new LinkedList("not",null);
        LinkedList middle = new LinkedList("too",tail);
        LinkedList head = new LinkedList("tricky",middle);
        assertEquals("not.",tail.getReversedSentence(""));
        assertEquals("not too tricky.",head.getReversedSentence(""));

It comes up with not.too tricky instead of not too tricky.

Edit: Contrusctor

public LinkedList(String word, LinkedList next) {
        this.word = word;
        this.next = next;
    }

Any hints?

what does the constructor for your linked list class look like? — nojo
– nojo, Commented Nov 1, 2010 at 17:27

irrelephant · Accepted Answer · 2010-11-01 23:04:46Z

1

Well... there's no need to use 2 methods, (important) --> because this method has String partialResult as a parameter. (You can if you want to and if helper methods are allowed in the solution, but it's unnecessary.) In other words, try to find some way to incorporate the current word with partialResult. Another hint: there is a solution that is 3 lines long (and properly formatted).

answered Nov 1, 2010 at 23:04

irrelephant

4,1112 gold badges28 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Snowman Over a year ago

I STILL cannot figure this out..Ive been working on it for hours please give me clearer hints!

irrelephant Over a year ago

@fprime: Let's see... instead of putting + this.word at the very end of the partialReturn = ... statement, try putting it inside the parameter when you call getReversedSentence() and see what you get. You can change things from there to get spacing to work.

irrelephant Over a year ago

@fprime, have you figured it out yet?

The Archetypal Paul · Accepted Answer · 2010-11-01 17:30:24Z

1

 public String getReversedSentence(String partialResult) {
        if (next==null) {
            partialResult+=this.word;
            return partialResult + ".";
        }
        else{
            partialResult=next.getReversedSentence(partialResult) + this.word; // <---
            return partialResult;
            }
    }

The problem is the line marked <---. The recursive call will eventuallyt return with the . appended (since it will recurse until it gets to the end of hte list, then add a ., return that and then you append this.word.

Since this is homework, I won't give a solution.

answered Nov 1, 2010 at 17:30

The Archetypal Paul

41.9k20 gold badges107 silver badges136 bronze badges

3 Comments

Snowman Over a year ago

Im still not figuring it out..what is my code currently doing thats erroneous?

The Archetypal Paul Over a year ago

See rsp's answer for a further hint

Ventral Over a year ago

Paul is right, partialResult will always be an empty string during the recursion down. You need to change partialResult before calling getReversedSentence.

rsp · Accepted Answer · 2010-11-01 18:01:16Z

1

What is going wrong is that the "." is appended to the word that is deepest in recursion, which is the first word in the reversed sequence.

You want to find a way to add the "." to the end of the reversed sequence, maybe by splitting your method in 2 methods where the one that calls the other knows something about the result.

answered Nov 1, 2010 at 18:01

rsp

23.4k6 gold badges59 silver badges72 bronze badges

Comments

Sanya Zahid · Accepted Answer · 2013-03-28 12:18:38Z

//--------------------------linklist class------------------------------------------------

import java.util.Stack;

public class Linklist {
    Stack <Character> a = new Stack <Character>();
    Node front; 
    Node back;
    Node Temp;

    public void insert (char d){
        Node newNode = new Node (d);
    if (front == null){
        front = newNode;
        back = newNode;
    }


    else {
        Temp = front;
        while (Temp != null){

            back= Temp;
        Temp = Temp.next ;
        }

        back.next = newNode;
    }


    }





    public void display(){
        Node T=front;
        System.out.print(T.data);
        T=T.next;
        while(T!=front)
        {
            System.out.print(T.data);
            T=T.next;
            if (T == null ){
                break;
            }
        }
    }


    public void reverse(){
    Linklist bb = new Linklist ();


        Node temp = front;
        while(temp != null ){
            if (temp.data != '_'){
 a.push(temp.data);

            }


            else{
        //char x =  
while (!a.isEmpty()){
    char pop = a.pop();
bb.insert(pop);


            }
bb.insert('_');
            }
            temp = temp.next;
        }// while end

        bb.display();

    }


}
//-------------------------------------------------------------------------------------


//------------------ test class
public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {

        queueLinklist a = new queueLinklist ();
a.insert('m');
a.insert('y');
a.insert('_');
a.insert('n');
a.insert('a');
a.insert('m');
a.insert('e');
a.insert('_');
a.insert('i');
a.insert('s');
a.insert('_');
a.insert('s');
a.insert('a');
a.insert('m');
a.insert('_');

a.display();
System.out.println(" ");
    a.reverse();
    a.reverse();
    }

}
// ---------- node class

public class Node {
char data;
Node next;

Node (){
    data= (Character) null ;
    next = null;
}

Node (char d){
    data = d;
    next = null;
}
}

Collectives™ on Stack Overflow

Help with backward recursion and LinkedList in Java

4 Answers 4

3 Comments

3 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

3 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related