Methoden Rekursive Methoden mit Rückgabeparameter

[veryck]

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]

 

[LimDul]

Wo ist deine Variable zahl definiert?

 

[MoxxiManagarm]

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:

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

 

[kneitzel]

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]

zahl ist als globale Variable definiert

 

[veryck]

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]

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.

 

[kneitzel]

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.

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]

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]

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.

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.