Sử dụng phương pháp đệ quy trong java

Question

cho bài tập về nhà Tôi đã được yêu cầu viết một phương thức chứa cho một danh sách liên kết tùy chỉnh. Tôi biết rằng phương pháp đệ quy cần phải có một trường hợp cơ sở và sau đó là đệ quy case.Tuy nhiên, tôi gặp một số rắc rối sự hiểu biết làm thế nào để viết các trường hợp đệ quy của phương pháp. Cho đến nay đây là những gì tôi đã viết, nhưng mã của tôi là thực hiện các trường hợp cơ sở nhiều hơn một lần. Bạn có thể vui lòng cho tôi một số hướng dẫn không?

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

Trước hết tôi muốn làm một cái gì đó như thế này:

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


} 

này ẩn chi tiết thực hiện từ người sử dụng và nó dừng lại danh sách của bạn khỏi bị ghi đè khi bạn chạy phương thức đó.

Answer 2

Để triển khai giải pháp đệ quy, bạn cần một phương thức phụ trợ cho contains. Phương thức phụ trợ phải có đối số bổ sung là Node để bắt đầu thử nghiệm. Phương thức công khai contains nên gọi phương thức phụ trợ và chuyển this.first làm nút bắt đầu. Phần còn lại của logic sau đó sẽ khá đơn giản để bạn tìm ra.

Answer 3

Từ những gì tôi thấy, mã của bạn sẽ trả về true khi statemnet khác đã được thực hiện một lần. Tôi nghĩ rằng những gì bạn cần làm là đặt giá trị boolean thành false mỗi lần bởi vì đệ quy hoạt động rất giống vòng lặp while và nếu các giá trị không được cập nhật, trường hợp cơ sở sẽ được thực hiện lặp đi lặp lại.