java - 在java中使用递归方法

Question

对于家庭作业，我被要求为自定义链表编写包含方法。我知道递归方法应该有一个基本案例，然后是递归案例。但是，我在理解如何编写该方法的递归案例时遇到了一些麻烦。到目前为止，这就是我所写的，但我的代码不止一次执行基本案例。你能给我一些指导吗？

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

Answer 1

首先，我喜欢做这样的事情：

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


}

这对用户隐藏了实现细节，并在您运行该方法时阻止您的列表被覆盖。

Answer 2

要实现递归解决方案，您需要一个用于contains. 辅助方法应该有一个额外的参数，它是Node开始测试的地方。公共contains方法应该调用辅助方法并this.first作为起始节点传递。其余的逻辑应该很容易让你弄清楚。

Answer 3

据我所见，一旦 else statemnet 执行一次，您的代码将返回 true。我认为您需要做的是每次都将布尔值设置为 false，因为递归的行为非常类似于 while 循环，如果值没有更新，则基本情况将一遍又一遍地执行。