Methoden Rekursive Methode zum zählen von Elementen

[ResidentSleeper]

[CODE lang="java" title="keine weiteren Attribute dürfen eingefügt werden"]public class PenguinRegister {

private Penguin penguin;
private PenguinRegister[] children = new PenguinRegister[26];[/CODE]

[CODE lang="java" title="Methode zum einfügen in das Register"]public PenguinRegister put (String name, Penguin penguin) {
int temp = -1;
PenguinRegister knotenToPenguin = this;
for(int i = 0; i < name.length(); i++) {
temp = name.charAt(i) - 65;
if(knotenToPenguin.getChildren()[temp] == null) { //befindet sich kein PenguinRegister an dieser Stelle, wird ein neues Register generiert und gespeichert
knotenToPenguin.getChildren()[temp] = new PenguinRegister();
knotenToPenguin = knotenToPenguin.getChildren()[temp];
}
else { //hier wird nur das PenguinRegister gespeichert, da der Knoten bereits existiert
knotenToPenguin = knotenToPenguin.getChildren()[temp];
}
}
knotenToPenguin.setPenguin(penguin); //der letzte Knoten wird mit dem Penguin belegt
return knotenToPenguin; //der mit dem Penguin belegter Knoten wird zurückgegeben
}[/CODE]

nun muss ich eine rekursive Methode int size() einfügen um die Anzahl aller gespeicherter Pinguine aufzuzählen.
Meine Idee war es einfach alle Register durchzugehen und dort zu schaun, ob ein Penguin gespeichert ist und wenn ja, die Zahl der Pinguine zu erhöhen.(ziemlich ineffizient aber es macht den job )

[CODE lang="java" title="bisheriger Ansatz"]public int size() {
PenguinRegister knotenToPenguin = this;
for(int i = 0; i < 26; i++) {
if (knotenToPenguin.getChildren() != null) {
knotenToPenguin.getChildren().size();
}
//TO-DO:
}
return /**/;
}[/CODE]

Mein Problem liegt jedoch darin, dass ich nicht weiß wie ich die Durchläufe bzw. die Anzahl der Pinguine, die != null sind zählen soll, ohne in der Klasse PenguinRegister selbst einen "Zähler" zu nitialisieren (was ich laut Aufgabenstellung nicht machen darf).

Falls mir jemand helfen kann würde ich mich sehr freuen ^^

 

[LimDul]

Den Rückgabewert von Zeile von 5 musst du irgendwo speichern. Dafür einfach eine lokale Variable nutzen. Und dann am Ende als Return Wert die Summe zurückgeben.

 

[kneitzel]

Bei rekursiven Funktionen ist der Aufbau doch immer gleich:
- Prüfung, ob man am Ende ist - dann hat man einen klar definierten Rückgabewert, den man zurück geben kann. (z.B. etwas ist leer -> size 0 wird zurück gegeben.)
- Wenn man nicht am Ende ist, dann wird rekursiv die Methode mit dem übrigen Part aufgerufen und das Ergebnis dann zusammen mit dem sozusagen "lokalen Ergebnis" zurück gegeben.


Und wenn Du bei 26 Teilbäumen die Anzahl brauchst, dann brauchst Du doch keinen Zähler in der Instanz sondern lediglich eine lokale Variable,

Und eine Methode aufzurufen, die etwas ermittelt wie size() und dann das Ergebnis zu ignorieren sollte generell immer die Alarmglocken läuten lassen. Also Ergebnis immer speichern und nutzen!

Und ganz nebenbei: Du hast doch die eigenes Instanz this - die kannst Du doch direkt verwenden - dazu brauchst du keine eigenständige lokale Variable.

Also eine lokale Variable size. Diese erzeugst Du und initialisierst sie auf einen richtigen Startwert! (Das wäre die Größe, wenn sonst bei den Children nichts dazu kommen würde?) Und dann rufst Du, so wie Du es fast schon gemacht hast, rekursiv size auf - nur eben muss dies dann zu der lokalen Variable hinzu addiert werden.

 

[ResidentSleeper]

Danke für die schnelle Antwort Ich versuch das mal wie ihr sagt zu implementieren. Hoffentlich krieg ichs hin

 

[ResidentSleeper]

public int size() {
        PenguinRegister knotenToPenguin = this;
        int summe = 0;
        for(int i = 0; i < 26; i++) {
            if (knotenToPenguin.getChildren()[i] != null) {
                summe = 1 + knotenToPenguin.getChildren()[i].size();
            }
        }
        return summe ;
    }

Meine Idee ist nach jedem Durchgang, wo ein Pinguinname steht eine 1 dazu zu addieren aber ich glaub ich verstehe rekursion nicht ganz so wie ich dachte.... Funktioniert leider immernoch nicht

 

[kneitzel]

Mal es Dir doch einfach einmal auf und gehe es von Hand durch.

Dein Baum hat 26 Unterbäume. Du bekommst die Summe des ersten und speicherst diesen mit +1 in summe.
Dann fragst Du den zweiten Unterbaum ab. Dann überschreibst Du das Ergebnis das du hattest mit dem neuen Wert.
Das ist, was Du wirklich machen willst?

Daher meine klare Bitte: Wenn Dir der Überblick fehlt, dann
a) Auf einem Zettel eine Skizze machen und dann selbst durchgehen. Was machst Du um zu dem Ergebnis zu kommen?
b) Vergiss im ersten Schritt Java! Als erstes musst Du den Ablauf verstanden haben. Dazu hilft es, das in einer Sprache zu formulieren, die Du gut verstehst. Also mach es erst einmal Umgangssprachlich!

 

[ResidentSleeper]

Eine Umsetzung von size() wäre:
1. Die Zweige der Wurzel werden auf eine existierende Kante durchsucht(von links nach rechts), existiert ein solches, wird diese Kante entlang zu dem Knoten x gesprungen woraufhin Schritt 1 nochmal ausgeführt wird (Knoten x entspricht dann wieder der "Wurzel")
2. Gelangt man so zu einem Knoten, der keine weiteren Unterbäume hat (also ein Blatt) so wird 1 auf die Summe addiert
3.Exception: Falls im ersten Schritt schon keine Kante zu finden ist, ist die Summe 0

Wäre dieser Ansatz schonmal richtig oder ist diese Denkweise schon nicht umsetzbar ?