Używanie metody rekursywnej w java

Question

do zadania domowego Poproszono mnie o napisanie metody zawierającej niestandardową, połączoną listę. Wiem, że metoda rekursywna powinna mieć podstawową, a następnie rekurencyjną sprawę.Jednak mam pewne problemy ze zrozumieniem, jak napisać rekurencyjny przypadek metody. Do tej pory to jest to, co napisałem, ale mój kod wykonuje zasadę zasadniczą więcej niż raz. Czy możesz dać mi jakieś wskazówki?

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

Przede wszystkim chciałbym zrobić coś takiego:

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


} 

Ten ukrywa szczegóły implementacji od użytkownika i zatrzymuje swoją listę z coraz nadpisane podczas uruchamiania tej metody.

Answer 2

Aby zaimplementować rozwiązanie rekurencyjne, potrzebna jest metoda pomocnicza dla contains. Metoda pomocnicza powinna mieć dodatkowy argument, którym jest Node, od którego należy rozpocząć testowanie. Publiczny metoda contains powinna wywołać metodę pomocniczą i przekazać this.first jako węzeł początkowy. Reszta logiki powinna być bardzo prosta, abyście mogli to zrozumieć.

Answer 3

Z tego co widzę, twój kod zwróci wartość true, gdy tylko raz wykonano statemnet else. Myślę, że musisz ustawić wartość boolowską na false za każdym razem, ponieważ rekursja działa bardzo podobnie do pętli while, a jeśli wartości nie są aktualizowane, to podstawowa sprawa byłaby wykonywana w kółko.