Rekursiver Pseudocode

anno

Mitglied
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

Top Contributor
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.

Java:
boolean ergebnis = (k%2) == 0

tut dasselbe.


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

anno

Mitglied
"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

Top Contributor
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

Top Contributor
"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.

Code:
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".

Code:
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).
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
E Hilfe bei rekursiver Funktion Java Basics - Anfänger-Themen 3
G Variable aktualisiert sich nicht in rekursiver Methode Java Basics - Anfänger-Themen 4
J Rekursiver Algorithmus Java Basics - Anfänger-Themen 9
K Rekursiver Vergleich von Textmuster und Text Java Basics - Anfänger-Themen 2
M Probleme bei rekursiver Zuordnung Java Basics - Anfänger-Themen 1
H Rekursiver Aufruf Java Basics - Anfänger-Themen 8
S Rekursiver InsertionSort ohne Schleife Java Basics - Anfänger-Themen 7
K Methoden Fibonacci in Array mit rekursiver Methoden Java Basics - Anfänger-Themen 19
4 Stack over flow bei rekursiver Tiefensuche Java Basics - Anfänger-Themen 5
T Rekursiver Methodenaufruf funktioniert nicht Java Basics - Anfänger-Themen 7
O Rekursiver Durchlauf verschachtelter Elemente Java Basics - Anfänger-Themen 1
B Quadratwurzel nach Heron in rekursiver Darstellung Java Basics - Anfänger-Themen 1
A Heap Space Error bei rekursiver Suche in Dateien trotz nur einer Zeile im Speicher Java Basics - Anfänger-Themen 26
W sysout in rekursiver methode Java Basics - Anfänger-Themen 4
E Problem bei rekursiver Berechnung des Binomialkoeffizienten Java Basics - Anfänger-Themen 5
S Probleme bei Ausgabe von rekursiver Methode (List) Java Basics - Anfänger-Themen 16
J Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig? Java Basics - Anfänger-Themen 2
D Binäre Suche für Integerarray in rekursiver Funktion Java Basics - Anfänger-Themen 5
O Faktorielle mit rekursiver Methode berechnen Java Basics - Anfänger-Themen 6
S Laufzeit bei rekursiver Methode messen Java Basics - Anfänger-Themen 6
N Unerklärlich: Rekursiver Algorithmus gibt falschen Datentyp zurück... Java Basics - Anfänger-Themen 4
J rekursiver Methodenaufruf Java Basics - Anfänger-Themen 12
D Datentypen Rekursiver Datentyp Java Basics - Anfänger-Themen 8
S Werte von rekursiver Methode Java Basics - Anfänger-Themen 5
Q rekursiver algo. Java Basics - Anfänger-Themen 16
M Potenz mithilfe rekursiver Funktion Java Basics - Anfänger-Themen 13
F Rekursiver Algorithmus Java Basics - Anfänger-Themen 5
C Frage zu negativen und positiven Exponenten in rekursiver Methode Java Basics - Anfänger-Themen 11
G Rekursiver Aufruf einer JSP über eine JavaScript-Funktion Java Basics - Anfänger-Themen 5
G PRoblem mit rekursiver float additions methode Java Basics - Anfänger-Themen 9
B rekursiver Funktionsaufruf Java Basics - Anfänger-Themen 2
E fehlermeldung bei rekursiver grafik Java Basics - Anfänger-Themen 11
F Problem bei rekursiver Binärsuche Java Basics - Anfänger-Themen 2
T Rekursiver Algorithmus: Türme von Hanoi Java Basics - Anfänger-Themen 8
s_1895 Pseudocode Naiver Algorithmus Java Basics - Anfänger-Themen 17
R Pseudocode erklären Java Basics - Anfänger-Themen 6
D Algorithmus in Pseudocode mit log2(n) Operationen erstellen Java Basics - Anfänger-Themen 3
D Hilfe um Pseudocode Analyse! Java Basics - Anfänger-Themen 1
P Eigenschaft eines imperativen Algo (Pseudocode) sofort erkennen Java Basics - Anfänger-Themen 1
H Pseudocode zu Java Java Basics - Anfänger-Themen 7
L Sudoku Backtracking Pseudocode Java Basics - Anfänger-Themen 3
E Hilfe bei Pseudocode-Frage Java Basics - Anfänger-Themen 5
B Methoden Pseudocode Java Basics - Anfänger-Themen 19
D Pseudocode Java Basics - Anfänger-Themen 3
J Von Pseudocode zu JavaCode Java Basics - Anfänger-Themen 7
B Pseudocode: rekursiv/nicht-rekursiv Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Neue Themen


Oben