Using Recursive method in java

Question

for homework I was asked to write a contain method for a custom linked list. I know that the recursive method should have a base case and then the recursive case.However, I am having some trouble understanding how to write the recursive case of the method. So far this is what I have written, but my code is executing the base case more than once. Can you please give me some guidance?

public class OrderedList {

private Node first;

//Constructor
public OrderedList() {
    this.first = null;
}

//Return the number of items in the list
public int size() {
    int counter = 0;
    Node pointer = this.first;
    while (pointer != null) {
        counter++;
        pointer = pointer.next;
    }
    return counter;
}

//Return an array of copies of the stored elements
public Comparable[] getStore() {

    Comparable[] elements = new Comparable[size()];
    Node pointer = this.first;
    if (this.first == null) {
        return elements;
    } else {
        int i = 0;
        while (pointer != null) {
            elements[i] = pointer.data;
            pointer = pointer.next;
            i++;
        }
        return elements;
    }

}
//true iff item matches a stored element
//Recursive

public boolean contains(Comparable item) {

    //Base case
    if (this.first == null) {

        return false;
    }
    Node pointer = this.first;
    this.first = this.first.next;

    if (pointer.data.compareTo(item) == 0) {

        return true;

    } 
    //Recursive case

    else {

        boolean info = contains(item);
        pointer.next = this.first;
        this.first = pointer;

        return info;
    }
}

Why are you changing the class variable in that method? You should be using a passed in Node, not this.first. You are changing the top of the list with every call of that method. You are destroying your list! — thatidiotguy
– thatidiotguy, Commented Jul 22, 2013 at 18:19

thatidiotguy · Accepted Answer · 2013-07-22 18:21:15Z

3

First of all I like to do something like this:

public boolean contains(Comparable item)
{
     return containsHelper(this.first, Comparable item);
}

private boolean containsHelper(Node node, Comparable item)
{
    //base case
    if(node == null)
    {   
         return false;
    }
    else
    {
         if(node.data.compareTo(item) == 0)
         {
             return true;
         }

         return containsHelper(node.next, item);
    }


}

This hides implementation details from the user and it stops your list from getting overridden when you run that method.

answered Jul 22, 2013 at 18:21

thatidiotguy

9,01114 gold badges66 silver badges109 bronze badges

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

2 Comments

jorgeAChacon Over a year ago

Is there a way for me to keep the method from overriding the list without having to implement a helper method?

thatidiotguy Over a year ago

@user1166061 Not really, this is the standard approach. Otherwise you would have to rely on the user of your code to pass in the first node which is ruining encapsulation. I mean you can see that I have reduced the amount of code you had so I am not sure why you would want to avoid the helper!

Ted Hopp · Accepted Answer · 2013-07-22 18:22:11Z

0

To implement a recursive solution, you need an auxiliary method for contains. The auxiliary method should have an additional argument that is the Node from which to start testing. The public contains method should call the auxiliary method and pass this.first as the start node. The rest of the logic should then be pretty simple for you to figure out.

answered Jul 22, 2013 at 18:22

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

4 Comments

jorgeAChacon Over a year ago

Is there a way for me to be able to conserve the list by using this method only?

Ted Hopp Over a year ago

@user1166061 - The auxiliary method can be written to not modify anything. I don't think you can write a recursive contains method without an auxiliary method.

thatidiotguy Over a year ago

@TedHopp I think the only way would be requiring the client to use code like list.contains(list.getFirst(), item) which is no good imo

Ted Hopp Over a year ago

@thatidiotguy - I agree that it would be no good to do it that way. It would also change the public interface, which would probably mean that the assignment was not done (even if the method worked correctly).

jfc8192 · Accepted Answer · 2013-07-22 18:23:47Z

0

From what I am seeing, your code will return true once the else statemnet have been executed once. I think what you need to do is to set the boolean value to false everytime because recursion acts very much like a while loop and if the values are not updated, the base case would be executed over and over again.

answered Jul 22, 2013 at 18:23

jfc8192

12 bronze badges

Collectives™ on Stack Overflow

Using Recursive method in java

3 Answers 3

2 Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related