在java中使用递归方法

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

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

来源

2013-07-22 jorgeAChacon

你为什么要改变该方法中的类变量？你应该使用传入的'Node'，而不是'this.first'。每次调用该方法时都会更改列表的顶部。你正在销毁你的名单！ – thatidiotguy

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

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


}

这对用户隐藏实现细节，并从当您运行方法得到覆盖停止列表中。

来源

2013-07-22 18:21:15 thatidiotguy

有没有一种方法让我保持方法免于重写列表而无需实施辅助方法？ – jorgeAChacon

@ user1166061不是，这是标准方法。否则，你将不得不依靠你的代码的用户传递第一个破坏封装的节点。我的意思是你可以看到我已经减少了你的代码量，所以我不确定你为什么要避免帮助者！ – thatidiotguy

非常感谢你 – jorgeAChacon

要实现递归解决方案，您需要一个用于contains的辅助方法。辅助方法应该有一个附加参数，即从中开始测试的Node。公众contains方法应调用辅助方法并通过this.first作为起始节点。其余的逻辑对你来说应该很简单。

来源

2013-07-22 18:22:11

有没有办法让我只用这种方法就能保存清单？ – jorgeAChacon

@ user1166061 - 可以编写辅助方法以不修改任何内容。我不认为你可以编写一个没有辅助方法的递归'contains'方法。 –

@TedHopp我认为唯一的方法是要求客户端使用类似'list.contains（list.getFirst（），item）'的代码'这是不好的imo – thatidiotguy

从我所看到的情况来看，一旦else statemnet被执行一次，你的代码将返回true。我认为你需要做的是每次将布尔值设置为false，因为递归非常像一个while循环，并且如果值没有更新，那么基本情况会一遍又一遍地执行。

来源

2013-07-22 18:23:47 jfc8192

在java中使用递归方法

回答

相关问题