Rekursiver Pseudocode

[anno]

Hallo Forum,

[Java]
Algorithmus tuWas(k)
if k = 0
then erg:= true
else erg:=not(tuWas(k-1))
return erg
[/Java]

Ich soll herausfinden was dieser Pseudocode macht. Ich komme nicht auf die Lösung. Wie geht man bei sowas speziell vor?

 

[Gucky]

Du gibst irgendwas oben hinein und guckst, was unten rauskommt.

Oder ein bisschen professioneller: Du guckst dir den Code Zeile für Zeile an und analysierst, was diese Zeile in Verbindung mit den Anderen tut.

Dem Algorithmus tuWas wird die typlose Variable k übergeben.
Wenn k = 0 gilt, so wird true zurückgegeben und tuWas ist beendet.

Wenn k nicht 0 ist, so ruft der Algorithmus sich selbst mit k-1 als Parameter auf.
Das passiert so lange, bis k = 0 gilt und der zuletzt aufgerufene tuWas true zurückgibt.
true wird vom aufrufenden tuWas "umgedreht" und wieder zurückgegeben. Dieser dreht den zurückgegebenen Wert wieder um und gibt ihn zurück. Das passiert so lange, bis keine Aufrufe von tuWas mehr vorhanden sind.


Im Prinzip ist es eine extrem komplizierte Art zu testen, ob eine Zahl grade ist, oder nicht.

boolean ergebnis = (k%2) == 0

tut dasselbe.


PS: so pseudo ist dieser Code gar nicht. Das sieht verdächtig nach Pascal aus.

 

[anno]

"true wird vom aufrufenden tuWas "umgedreht" und wieder zurückgegeben. Dieser dreht den zurückgegebenen Wert wieder um und gibt ihn zurück. Das passiert so lange, bis keine Aufrufe von tuWas mehr vorhanden sind."

Verstehe diesen Teil nicht.

 

[Gucky]

Wenn wir einmal ein bisschen Tiefer in die Programmierung einsteigen, sehen wir, dass es den sog. StackTrace gibt. In diesem sind sämtliche Algorithmen gespeichert, die vom aktuellen Thread aufgerufen und noch nicht beendet wurden. In der Reihenfolge ihres Aufrufes.

Bei einem rekursiven Algorithmus ist dieser rekursive Algorithmus mehrfach an den letzten Stellen, da er mehrfach von sich selbst aufgerufen wird.

Platz Eins ist im Folgenden der zuletzt aufgerufene Algorithmus im StackTrace.

Der Erste aus dieser Reihe nimmt den Wert true und gibt ihn an den Platz zwei des StackTraces zurück, wird beendet und aus dem StackTrace gelöscht.
Der nun Erste und vormals Zweite nimmt dieses true, dreht es um (zu false), gibt dieses false an den Algorithmus, der nun Platz 2 ist zurück, wird beendet und aus dem StackTrace gelöscht.

Das passiert so lange, bis alle Aufrufe von tuWas aus dem StackTrace entfernt wurden.

 

[Joose]

"true wird vom aufrufenden tuWas "umgedreht" und wieder zurückgegeben. Dieser dreht den zurückgegebenen Wert wieder um und gibt ihn zurück. Das passiert so lange, bis keine Aufrufe von tuWas mehr vorhanden sind."

Verstehe diesen Teil nicht.

erg:=not(tuWas(k-1))

Es wird "tuWas(...)" aufgerufen und das Ergebnis negiert ("not"). Dieser negierte Wert wird nun auf der Variable Ergebnis gespeichert und dieses wird von der Methode zurückgelieftert an den Aufrufer.

Sprich die Methode "tuWas(...)" ruft sich solange selber auf bis "k==0" ist. In diesem Fall wird "true" als Ergebnis zurückgegeben. Dieses Ergebnis wird jedem "tuWas(...)" Aufruf im Stack negiert und "weiter nach oben gereicht".

public boolean tuWas(int k) {
   System.out.println("ANFANG - tuWas mit K = " + k);
   boolean erg = false;
   if (k == 0) {
      System.out.println("K = 0 -> true");
      erg = true;
   } else {
      erg = !tuWas(k-1); // ! steht für das not
      System.out.println("erg = " + erg");
   }
   System.out.println("ENDE - tuWas mit K = " + k + ", erg = " + erg);
   return erg;
}

Hier hast du den Pseudocode in Java geschrieben inkl Konsolenausgaben.
Führe diese Methode aus mit k = 10. Schaue dir die Ausgaben an und du solltest den Code verstehen.

Hinweis: Wann immer du einen Pseudocode vor dir hast und du willst erfassen was er macht -> wandle ihn in eine Sprache um (in diesem Fall Java) und führe den Code aus (wenn möglich).