Rekursive Methoden

[Luca H]

Hallo, ich hätte eine Frage.
Und zwar sollen wir eine Rekursive Methode schreiben, in der wir ein Integer Array und einen Integerwert n bekommen. Nun sollen wir überprüfen, ob dieser Wert im Array vorkommt, wenn ja soll nur dann true zurückgegeben werden, wenn die Anzahl der vorkommenden Werte n gerade ist. Falls ungerade dann false. Nun habe ich das Problem, dass ich versuche, jeden Index mit n zu vergleichen und wenn dieser gleich ist einen counter zählen lasse.

Nun zum Problem: Wenn ich am ende die Methode rekursiv aufrufe initialisiert er mein index i wieder auf 0.

Code folgt

 

[Luca H]

public class Functionality {
    
    public static void main(String[] args) {
        evenNumberOf(2, new int[] {1,2,3,2});
        
    }
    
    public static boolean evenNumberOf(int n, int[] a) {
        int i = 0 ;
        int counter = 0;
        if(a == null || a.length == 0) {
            return false;
        } else {
            if(a[i] == a.length -1 ) {
                if(counter % 2 == 0) {
                    System.out.println("true");
                    return true;
                    
                } else System.out.println("false");
                    return false;
                
            } else {
            if(a[i] == n) {
                counter++;
                i++;
                return evenNumberOf(n,a) ;
            } else {
                i++;
                return evenNumberOf(n,a) ;
            }
            
                
            
            }
        }

 

[mihe7]

Wenn Du die Signatur der Methode nicht ändern darfst, funktioniert das so natürlich nicht. Da musst Du Dir was anderes überlegen.

Tipp:

Spoiler

Ein Array [a,b,c,d] kann man als Element a und ein Array [b,c,d] betrachten.

 

[httpdigest]

Kannst du einmal die genaue (literally) Aufgabenstellung schicken? Vielleicht darfst du ja auch eine Hilfsmethode schreiben, die die eigentliche rekursive Methode ist.

 

[Luca H]

Das wäre die Aufgabe:

Implementieren Sie eine statische-public Methode mit dem Namen
"evenNumberOf" in der Klasse "Functionality". Die Methode bekommt als
Eingabeparameter einen Integer-Wert n und ein Integer-Array und gibt einen
Boolean zurück.

evenNumberOf soll rekursiv (!) feststellen, ob im Array die Anzahl des Wertes
n gerade ist. Wenn ja, soll true zurueckgegeben werden, ansonsten false. Wenn
das eingegebene Array null ist oder die Laenge 0 hat, soll ebenso false
zurueckgegeben werden.

Beispiel: evenNumberOf(2, new int[] {1,2,3,2}) ---> true

evenNumberOf(1, new int[] {1,2,3,2}) ---> false

Hinweis: Loesen Sie das Problem nicht iterativ, d.h. verwenden Sie keine
Schleifen! Die Tests testen nicht auf rekursive Implementation, sondern nur
die korrekten Rueckgaben Ihrer Methode.

 

[iamcytrox]

Das ist wirklich ein interessantes Problem. Gibts etwas hierzu?

 

[httpdigest]

Was meinst du mit, ob es "etwas" hierzu gibt?

 

[iamcytrox]

Anregungen wie man das Problem lösen kann. Ich habe zwar nicht genau das gleiche Problem, allerdings ein ähnliches und ich bin auf der Suche nach Lösungsansätzen. Da der Topic noch recht aktuell ist, hatte ich gehofft, dass jemand einen Ansatz hat. Durchgekautes möchte ich natürlich nicht, ich möchte es selbst lernen. Allerdings bin ich hier maßlos überfordert 😀

 

[fhoffmann]

Wenn die erste Zahl im Array mit der gesuchten Zahl übereinstimmt, gib zurück, ob die gesuchte Zahl im Rest des Arrays ungerade oft vorkommt (nicht gerade oft vorkommt),
ansonsten gib zurück, ob die gesuchte Zahl im Rest des Arrays gerade oft vokommt.

 

[httpdigest]

Ich denke, ein "key insight" hier ist, dass man eine Hilfsmethode braucht, die selbst rekursiv ist, denn man kann mit der Signatur der vorgegebenen Methode nicht die drei unterschiedlichen nötigen Zustände "kein Match", "ungerader Match", "gerader Match" abbilden.

 

[kneitzel]

Ich denke, ein "key insight" hier ist, dass man eine Hilfsmethode braucht, die selbst rekursiv ist, denn man kann mit der Signatur der vorgegebenen Methode nicht die drei unterschiedlichen nötigen Zustände "kein Match", "ungerader Match", "gerader Match" abbilden.

Das ist doch so nicht vorgegeben. Das "kein Match" gibt es nicht. Kein match wäre 0 und gerade. Die Sonderbehandlung ist ja nur: Array null oder Länge 0:

Wenn
das eingegebene Array null ist oder die Laenge 0 hat, soll ebenso false
zurueckgegeben werden.

Damit hat man eine Prüfung, die zwar nur beim ersten Aufruf interessant ist, aber problemlos jedes Mal laufen kann.
Rekursion-Abbruch muss halt sein, wenn das Array Größe 1 hat.
Und sonst ist es halt ein Vergleich des Elements an 0 + Rekursiver Aufruf Rest. (Was man natürlich richtig zusammen packen muss - das habe ich jetzt mal absichtlich nicht vorgegeben)

Die Hilfsroutine würde ich aber dennoch machen um dann halt noch den Parameter aktuellerIndex mitzugeben. Damit vermeidet man das viele Array kopieren.

 

[httpdigest]

Das ist doch so nicht vorgegeben. Das "kein Match" gibt es nicht. Kein match wäre 0 und gerade. Die Sonderbehandlung ist ja nur: Array null oder Länge 0:

Und wie willst du dann folgende oben genannte Anforderung lösen?

Wenn
das eingegebene Array null ist oder die Laenge 0 hat, soll ebenso false
zurueckgegeben werden."

Du weißt ja nicht, ob das nun aus einem rekursiven Fall eingetreten ist, oder im ersten Aufruf.
Denn wenn du rekursiv abgestiegen bist bis zum Fall, wo dein Restarray noch eine Lange von 0 hat, dann kannst du vorher ja schon Elemente gefunden haben oder auch nicht.

 

[fhoffmann]

Rekursion-Abbruch muss halt sein, wenn das Array Größe 1 hat.

 

[kneitzel]

Du weißt ja nicht, ob das nun aus einem rekursiven Fall eingetreten ist, oder im ersten Aufruf.

Wenn Du nur bis zu einem Element runter gehst, dann hast Du den Fall ja nicht. Das kann also nur beim ersten Aufruf auftreten. Die Wahl des Abbruchkriteriums kann das also lösen. Den Algorithmus hatte ich auch schon skizziert (weiss den Thread aber nicht mehr und bin zu faul zu suchen):

1. Array null oder array length 0? -> Ende mit Return-Wert Sonderbehandlung -> Nicht Teil der eigentlichen Rekursion
2. Array length 1? Rückgabe ob der Wert nicht gleich dem zu prüfenden Wert ist.
3. Wenn erster Wert == gesuchter Zahl: return !rekursiverAufruf für RestArray
Sonst return rekursiverAufruf für Restarray

(Den Punkt 3 kann man auch zusammen fassen ohne if mit nur einem logischen Ausdruck - aber so ist es leichter verständlich. Und die eigentliche Rekursion ist 2 und 3, da 1 sozusagen nur die Validierung ist, die eigentlich nur einmal stattfinden muss und die aber beliebig oft kommen kann.)

Edit: Return Wert bei 2 war falsch. true heisst ja "gerade" Anzahl, daher Prüfung auf "nicht gleich" und nicht auf gleich.

 

[kneitzel]

Was mir im ersten Thread zu diesem Thema, bei dem ich bei dem Lösungsansatz Hilfen gegeben habe, wichtig war:
Ich sehe das zweigeteilt:
a) Wir haben ganz klar die Rekursion. Die muss man einmal schreiben.
b) Wir haben eine Sonderbehandlung. Die kommt als zweiten Schritt dazu.

"Nicht zuviel auf einmal machen und sich dabei verzetteln!" war die Aussage, die ich rüber bringen wollte. Gerade am Anfang neigt man halt genau zu sowas. Direkt in Java etwas programmieren wollen - Stift und Zettel sind aber normale Hilfsmittel. (Klar, die Komplexität steigt, aber die Whiteboards sind in Entwicklerteams extrem wichtige Tools und erfüllen genau die Funktion. Abläufe / Algorithmen werden schnell skizziert und ggf. besprochen.)

Mit der Zeit kommt mehr Erfahrung, aber genau dieser Ansatz wird dann ggf. auch wieder forciert (z.B. bei TDD). Aber auch in der Agilen Darstellung könnten das schon fast 2 User Stories sein (Ok, etwas das ist wohl doch etwas übertrieben 🙂 ).

Es läuft halt immer alles sehr stark auf das "Teile und Herrsche" hinaus. Das, was Uncle Bob als Grundlage des Agilen Arbeitens ausgedrückt hat. Viele einfache, kurz und schnell zu erledigenden Dinge machen. (Ist jetzt so aus dem Kopf heraus nur sinngemäß ... habe ich leider nicht genauer im Kopf.)

Das nur etwas zu den Hintergründen bei dieser Unterstützung. Ist hoffentlich nicht zu verwirrend.