在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中使用遞歸方法

回答

相關問題