Methoden Rekursive Methoden mit Rückgabeparameter

veryck

Mitglied
Hallo, ich bin ein ziemlicher Anfänger, habt also bitte Nachsicht mit mir.

In der Schule behandeln wir gerade das Thema Binäre Bäume und wir sollten eine Methode programmieren, die die Anzahl der Blätter ausgibt. Das habe ich auch, die Methode funktioniert auch, aber mein Lehrer meinte, sie wäre (syntaktisch) falsch und dass er mir in einer Klausur Punkte für den Code abgezogen hätte. Er meint, wenn ich die Methode anzahlBlätter() rekursiv aufrufe (Zeile 3 und 6), gibt sie einen Zahlenwert, den ich verarbeiten muss. In meinem Code wäre es also so, als ob ich einfach eine Zahl geschrieben hätte. Ich verstehe seine Argumentation ehrlich gesagt nicht, kann mir jemand weiterhelfen?
Danke im Voraus!

[CODE lang="java" highlight="3,6"]public int anzahlBlätter(BinaryTree b){
if(b.getLeftTree().getContent()!=null){
this.anzahlBlätter(b.getLeftTree());
}
if(b.getRightTree().getContent()!=null){
this.anzahlBlätter(b.getRightTree());
}
if (b.getLeftTree().getContent()==null && b.getRightTree().getContent()==null){
zahl = zahl + 1;
}
return zahl;
}[/CODE]
 

MoxxiManagarm

Top Contributor
Vermutlich ist zahl bei dir eine Klassenvariable. Er meint damit, dass zahl eine Variable in der Methode sein sollte. Die zahl, welche du zurückgibst, verwendest du aktuell nicht. Es müsste z.B. so aussehen:

Java:
public int anzahlBlätter(BinaryTree b) {
  // Abbruchbedingung, Blatt gefunden
  if (b.getLeftTree().getContent()==null && b.getRightTree().getContent()==null){ 
    return 1;
  }

  int zahl = 0;
  if (b.getLeftTree().getContent() != null) {
   zahl += anzahlBlätter(b.getLeftTree());
  }
  if (b.getRightTree().getContent() != null) {
    zahl += anzahlBlätter(b.getRightTree());   
  }
  return zahl;
}
 
K

kneitzel

Gast
Die Problematik ist ja einfach: Die Methode gibt etwas zurück und du ignorierst es. Das ist etwas, das ganz klar darauf hin deutet, dass es ein Problem beim Design gibt.

Und es wird auch ganz schnell deutlich: anzahlBlätter gibt nicht die Anzahl der Blätter des übergebenen Teilbaums zurück. Das merkst Du ja an den Aufrufen.... Wenn erst links und dann rechts aufgerufen wird, dann gibt der zweite Aufruf auch die Blätter des ersten Aufrufs mit aus.

Die Logik ist also nicht sauber implementiert und der Punkteabzug gerechtfertigt.

Die Logik sollte immer relativ einfach aufgebaut sein:
a) Abbruchbedingung mit sinnvoller Rückgabe.
b) Rückgabe einer Berechnung, die vorhandenes Verwendet.

Habe ich schon paar Stunden nicht geschrieben: Formuliere es immer erst sauber.
a) Abbruchbedingung: Wenn es sich um ein Blatt handelt, dann gib 1 zurück.
b) Ergebnis ist Anzahl Blätter Linker-Teilbaum + Anzahl Blätter Rechter Teilbaum.

Hier muss man dann aber noch aufpassen: Was ist, wenn es einen Teilbaum nicht gibt? Das würde ich anders abhandeln, indem ich a aufteile:
-> Gegebener Teilbaum ist null? -> return 0;
-> Gegebener Teilbaum ist blatt? -> return 1;
-> return Summe Rechts + Summe Links

Also zwei Abbruchbedingungen und dafür ein schöner rekursiver Aufruf ohne if Abfragen ... Aber das ist Geschmackssache...
 

veryck

Mitglied
Die Problematik ist ja einfach: Die Methode gibt etwas zurück und du ignorierst es. Das ist etwas, das ganz klar darauf hin deutet, dass es ein Problem beim Design gibt.

Und es wird auch ganz schnell deutlich: anzahlBlätter gibt nicht die Anzahl der Blätter des übergebenen Teilbaums zurück. Das merkst Du ja an den Aufrufen.... Wenn erst links und dann rechts aufgerufen wird, dann gibt der zweite Aufruf auch die Blätter des ersten Aufrufs mit aus.

Die Logik ist also nicht sauber implementiert und der Punkteabzug gerechtfertigt.

Die Logik sollte immer relativ einfach aufgebaut sein:
a) Abbruchbedingung mit sinnvoller Rückgabe.
b) Rückgabe einer Berechnung, die vorhandenes Verwendet.

Habe ich schon paar Stunden nicht geschrieben: Formuliere es immer erst sauber.
a) Abbruchbedingung: Wenn es sich um ein Blatt handelt, dann gib 1 zurück.
b) Ergebnis ist Anzahl Blätter Linker-Teilbaum + Anzahl Blätter Rechter Teilbaum.

Hier muss man dann aber noch aufpassen: Was ist, wenn es einen Teilbaum nicht gibt? Das würde ich anders abhandeln, indem ich a aufteile:
-> Gegebener Teilbaum ist null? -> return 0;
-> Gegebener Teilbaum ist blatt? -> return 1;
-> return Summe Rechts + Summe Links

Also zwei Abbruchbedingungen und dafür ein schöner rekursiver Aufruf ohne if Abfragen ... Aber das ist Geschmackssache...
Das habe ich vielleicht etwas unglücklich formuliert, aber ich gebe ja beim allerersten Methodenaufruf einen Baum mit und soll von diesem Baum die Gesamtzahl der Blätter ermitteln, bzw. ausgeben, nicht die der einzelnen Teilbäume. Wäre es dann nicht korrekt sowohl die Blätter des ersten Aufrufs auch im zweiten Aufruf mitauszugeben? Und wie stelle ich die Abbruchbedingungen ohne die if-Abfragen auf?
 

MoxxiManagarm

Top Contributor
zahl ist als globale Variable im Konstruktor definiert.
Ja das ist falsch. Die Methode ist damit nicht pure.

Stell dir mal vor du würdest in einem Garten Äpfel aufsammeln.

In Variante 1 (impure) würdest du alle Äpfel zu einem Freund werfen und weiterlaufen, weitersammeln bis du alle Äpfel aufgehoben und zum Freund geworfen hast. Am Ende zählst du die Äpfel. Der Freund war aber hungrig und hat einen gegessen, das lag nicht unter deiner Kontrolle, das ist blöd.

In Variante 2 (pure) würdest du eine Schubkarre mit dir führen und die Äpfel gesammelt abgeben und zählen. Der Schubkarren war immer neben dir, mit den Äpfeln konnte nichts passieren, was du nicht gesehen hättest.


In deinem "funktionierenden" Fall hat keine andere Methode die globale Variable zahl verändert, aber es könnte eine geben und darum geht es. In größeren Projekt könntest du so etwas ganz schnell übersehen. Außerdem müsstest du darauf achten, dass du zahl bei einem neuen Zähldurchlauf erst einmal zurücksetzt bevor du nochmal zählst.
 
K

kneitzel

Gast
Das habe ich vielleicht etwas unglücklich formuliert, aber ich gebe ja beim allerersten Methodenaufruf einen Baum mit und soll von diesem Baum die Gesamtzahl der Blätter ermitteln, bzw. ausgeben, nicht die der einzelnen Teilbäume. Wäre es dann nicht korrekt sowohl die Blätter des ersten Aufrufs auch im zweiten Aufruf mitauszugeben? Und wie stelle ich die Abbruchbedingungen ohne die if-Abfragen auf?
Du sollst die Anzahl der Blätter ausgeben und sollst (oder willst) dazu rekursiv vorgehen. Rekursion bedeutet ja, dass Du die Funktion wiederholt aufrufst.

Nur eben wird bei einer Rekursion nicht außerhalb in einer Instanzvariable etwas gezählt. Rekursive Formeln sind immer in etwa so aufgebaut:
f(x) =
für x = 0: 0
sonst: f(x-1) + x

Und nicht anders wird es in der Regel auch bei den Methoden wir bei Dir aufgebaut:
Anzahl der Blätter des Teilbaums ist:
- wenn kein Teilbaum übergeben wurde: 0
- Wenn der Teilbaum keine Blätter hat: 1
- sonst: Anzahl Blätter vom rechten Teilbaum + Anzahl Blätter vom Linken Teilbaum.

So in der Art wird es immer aufgebaut.

Und die if Anweisungen wurden nie kritisiert.

Und um Deinen Code korrekt zu halten: Lösche die Instanzvariable zahl und komm ohne diese aus.

Java:
public int anzahlBlätter(BinaryTree b){
        int zahl = 0;
        if(b.getLeftTree().getContent()!=null){
            zahl = this.anzahlBlätter(b.getLeftTree());
        }
        if(b.getRightTree().getContent()!=null){
            zahl += this.anzahlBlätter(b.getRightTree());   
        }
        if (b.getLeftTree().getContent()==null && b.getRightTree().getContent()==null){
            zahl =  1;
        }
        return zahl;
    }
Das wäre dann vermutlich der Code, der dann auch bei Dir heraus kommen würde.
 

veryck

Mitglied
Wo ist deine Variable zahl definiert?
Ja das ist falsch. Die Methode ist damit nicht pure.

Stell dir mal vor du würdest in einem Garten Äpfel aufsammeln.

In Variante 1 (impure) würdest du alle Äpfel zu einem Freund werfen und weiterlaufen, weitersammeln bis du alle Äpfel aufgehoben und zum Freund geworfen hast. Am Ende zählst du die Äpfel. Der Freund war aber hungrig und hat einen gegessen, das lag nicht unter deiner Kontrolle, das ist blöd.

In Variante 2 (pure) würdest du eine Schubkarre mit dir führen und die Äpfel gesammelt abgeben und zählen. Der Schubkarren war immer neben dir, mit den Äpfeln konnte nichts passieren, was du nicht gesehen hättest.


In deinem "funktionierenden" Fall hat keine andere Methode die globale Variable zahl verändert, aber es könnte eine geben und darum geht es. In größeren Projekt könntest du so etwas ganz schnell übersehen. Außerdem müsstest du darauf achten, dass du zahl bei einem neuen Zähldurchlauf erst einmal zurücksetzt bevor du nochmal zählst.
Ja, das hatte er auch bemängelt. Deine Begründung ergibt Sinn, danke für die schnelle Antwort
 

veryck

Mitglied
Du sollst die Anzahl der Blätter ausgeben und sollst (oder willst) dazu rekursiv vorgehen. Rekursion bedeutet ja, dass Du die Funktion wiederholt aufrufst.

Nur eben wird bei einer Rekursion nicht außerhalb in einer Instanzvariable etwas gezählt. Rekursive Formeln sind immer in etwa so aufgebaut:
f(x) =
für x = 0: 0
sonst: f(x-1) + x

Und nicht anders wird es in der Regel auch bei den Methoden wir bei Dir aufgebaut:
Anzahl der Blätter des Teilbaums ist:
- wenn kein Teilbaum übergeben wurde: 0
- Wenn der Teilbaum keine Blätter hat: 1
- sonst: Anzahl Blätter vom rechten Teilbaum + Anzahl Blätter vom Linken Teilbaum.

So in der Art wird es immer aufgebaut.

Und die if Anweisungen wurden nie kritisiert.

Und um Deinen Code korrekt zu halten: Lösche die Instanzvariable zahl und komm ohne diese aus.

Java:
public int anzahlBlätter(BinaryTree b){
        int zahl = 0;
        if(b.getLeftTree().getContent()!=null){
            zahl = this.anzahlBlätter(b.getLeftTree());
        }
        if(b.getRightTree().getContent()!=null){
            zahl += this.anzahlBlätter(b.getRightTree());  
        }
        if (b.getLeftTree().getContent()==null && b.getRightTree().getContent()==null){
            zahl =  1;
        }
        return zahl;
    }
Das wäre dann vermutlich der Code, der dann auch bei Dir heraus kommen würde.
Danke für die schnellen und ausführlichen Antworten. Ich denke, ich habe es jetzt verstanden.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
emreiu Methoden Rekursive Methoden Runter- & Hochzählen Java Basics - Anfänger-Themen 2
L Rekursive Methoden Java Basics - Anfänger-Themen 14
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
K Rekursive Methoden Java Basics - Anfänger-Themen 15
S rekursive methoden Java Basics - Anfänger-Themen 5
T Rekursive Methode Java Basics - Anfänger-Themen 13
Viktor A. Kaiser Rekursive Algorithmen Java Basics - Anfänger-Themen 9
til237 Iterative Methode in rekursive Methode umschreiben Java Basics - Anfänger-Themen 4
new_to_coding Rekursive Reihe implementieren Java Basics - Anfänger-Themen 1
J Rekursive Funktion und return statement Java Basics - Anfänger-Themen 3
S Rekursive Kombinationen Java Basics - Anfänger-Themen 6
P9cman Tipps für Rekursive Aufgaben mit Strings oder allgemein Java Basics - Anfänger-Themen 2
Csircc Rekursive Methode Stack Overflow Java Basics - Anfänger-Themen 10
schredder Rekursive Quadratzahlen - Ergebnisprozedur Java Basics - Anfänger-Themen 1
A Rekursive Implementation eines Codes Java Basics - Anfänger-Themen 4
C Rekursive Methode in Interative Methode umwandeln Java Basics - Anfänger-Themen 17
G Rekursive Methode mit 2 Aufrufen Java Basics - Anfänger-Themen 1
J Rekursive Folge (a=a-1) Java Basics - Anfänger-Themen 9
M Rekursive Java-Methode Java Basics - Anfänger-Themen 13
G Rekursive Methode liefert augenscheinlich keinen boolean-Wert zurück. Java Basics - Anfänger-Themen 4
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
MiMa Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
G Rekursive Methode Java Basics - Anfänger-Themen 3
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Neue Themen


Oben