Rekursion

[infomania383838]

Hallo Community, könnte mir jemand eine Hilfestellung geben und erklären wie diese Rekursion funktioniert? Es ist Teil einer Probeklausur und da mir diese rekursiven Aufrufe Probleme bereiten, wäre ich froh darüber wenn ihr mir soweit helfen könnten, dass ich es selber komplett nachvollziehen kann.

public class RekursionProbeklausurAufgabe7 {
     static void ery(int n) {
         if (n == 0)
    
         return;
      ery( n-1);
     
      A();
      yre( n-1);
     }
     static void yre(int n) {
         if (n == 0)
         return;
             ery( n-1);
             B();
             yre( n-1);
     }
     static void A() {
     System.out.print("A");
     }
     static void B() {
     System.out.print("B");
}
      public static void main(String[] args) {
      int n = 4;
      ery(n);
      System.out.println();
      }
      }

Eine Aufgabe ist zu bestimmen, welche die ersten 8 Ziffern der Ausgabe bei einer Parameterübergabe von n= 4 sind. Die ersten 8 Ziffern wären AABAABBA, aber wie wird dieser Aufruf denn genau abgearbeitet?

Ein anderer Aufgabenteil fordert die genaue Anzahl der ausgegebenen Ziffern bei einer Paramterübergabe von n= 7. Wie kann ich denn die Anzahl der Ziffern im Kopf berechnen?(Bei einer Klausur haben wir standardmäßig keine Entwicklungsumgebung und durchschnittlich nur ca. 6min pro Aufgabe).

Über Vorschläge und Denkanstöße freue ich mich sehr

 

[MoxxiManagarm]

ery(4) von main
--ery(3) von ery(4)
----ery(2) von ery(3)
------ery(1) von ery(2)
--------ery(0) von ery(1) //return
--------A() von ery(1) // Ausgabe A
--------yre(0) von ery(1) // return
------A() von ery(2) // Ausgabe A
------yre(1) von ery(2)
--------ery(0) von yre(1) // return
--------B() von yre(1) // Ausgabe B
--------yre(0) von yre(1) // return
----A() von ery(3) // Ausgabe A
----yre(2) von ery(3)
------ery(1) von yre(2)
--------ery(0) von ery(1) // return
--------A() von ery(1) // Ausgabe A
--------yre(0) von ery(1) // return
------B() von yre(2) // Ausgabe B
------yre(1) von yre(2)
--------ery(0) von yre(1) // return
--------B() von yre(1) // Ausgabe B
--------yre(0) von yre(1) // return
--A() von ery(4) // Ausgabe A
--yre(3) von ery(4)
----// geht weiter, aber die ersten 8 Zeichen sind damit erreicht.

 

[tommysenf]

Ersetze
ery(n) durch ery(n-1) A yre(n-1)
sowie
yre(n) durch ery(n-1) B yre(n-1)


ery(4)
ery(3) A yre(3)
ery(2) A yre(2) A ery(2) B yre(2)
ery(1) A yre(1) A ery(1) B yre(1) A ery(1) A yre(1) B ery(1) B yre(1)
ery(0) A yre(0) A ery(0) B yre(0) A ery(0) A yre(0) B ery(0) B yre(0) A usw...

 

[MoxxiManagarm]

ery(1) hat 1 Ausgabe
ery(2) hat 3 Ausgaben
ery(3) hat 7 Ausgaben
...

ery(4) hätte 15 Ausgaben
usw.

n(x) = n(x-1) * 2 + 1

 

[infomania383838]

Danke für die Antworten, gehe das gleich mal alles durch

 

[infomania383838]

Ich habe immer noch meine Probleme zu verstehen wie genau dieser Aufruf abgearbeitet wird. Bei n=1 macht es Sinn, dass nur die erste Methode abgearbeitet werden kann und ich ein A als Ergebnis bekomme. Bei n=2 kommen zu dem A noch ein AB dazu, weil ich nun eine 2 habe und jede Methode zusätzlich einmal durchlaufen werden kann. Ich verstehe wie die Anzahl der Ziffern zustande kommt, aber nicht in welcher Reihenfolge und nach welcher Struktur die einzelnen Methoden abgearbeitet werden und wann ich von ery zu yre springe und ebend ein B anstatt A gedruckt wird. Ich finde die Darstellung von MoxxiManagarm gut, könnte die in einer Erklärung von jemandem aufgegriffen werden?

 

[MoxxiManagarm]

Eigentlich finde ich die Ersetzungsmethode von timmy besser. Du musst einfach nur dem Programmablauf folgen. Aber dabei wird erst ein Aufruf vollständig abgerarbeitet, also in ery (4) wird ery(3) erst vollständig durchlaufen bevor A() und yre(3) später erfolgen. Das Gleiche geschieht in ery(2), ery(1) und auch den yre(n) Aufrufen.

 

[infomania383838]

Also ich hoffe ich bin jetzt auf dem richtigem Pfad. Nach der Ersetzungsmethode wird also bei einem Aufruf von z.B ery(4) jeder Aufruf erstmal abgearbeitet, ich bekomme dann ery(3), dann das A() und zum Schluss das yre(3) , sodass ich zuerst zu einem A komme.

Aber wenn ich dann z.B bei ery(2) angelange kommt zu dem bereits vorhandenen A noch ein AB hinzu. Aber wie kommt dieses AB zustande? Ich arbeite also erst wieder ery(2) und A() und dann erst die yre(2) Methode ab, aus ery(2) entsteht die Ausgabe A und das yre(2) ruft die Ausgabe B aus, sodass ich dann das AAB als Erbenis habe.

Jetzt bin ich bei ery(1) und übernehme das AAB von vorhin. Dort wird dann ein AABB noch drangehangen, sodass das Ergebnis AABAABB wird. Könnte mir jemand sagen wie das AABB zu erklären ist? Ich komme einfach nicht darauf wie genau dieses Aufruf abgearbeitet wird.

 

[Meniskusschaden]

Aber wenn ich dann z.B bei ery(2) angelange kommt zu dem bereits vorhandenen A

Wenn du (das erste Mal) bei ery(2) ankommst, ist noch gar kein A vorhanden, denn der Aufruf von ery(2) ist ein Bestandteil der Abarbeitung von ery(3), welche zu diesem Zeitpunkt also noch nicht abgeschlossen ist, so dass der Aufruf von A() noch gar nicht erreicht wurde.

In der Auflösung von @tommysenf sieht man das auch sehr gut. Du kannst das noch eine Stufe weiter führen und die Aufrufe von ery(0) und yre(0) durch nichts ersetzen (also ersatzlos entfernen), denn die beiden Aufrufe geben ja nichts aus und führen auch keine weiteren Methodenaufrufe durch.

Falls dein Originalcode genauso wie im Eröffnungsposting formatiert sein sollte, würde ich das auch noch in Ordnung bringen. Die fehlerhaften Einrückungen verwirren nur.

 

[temi]

wird also bei einem Aufruf von z.B ery(4) jeder Aufruf erstmal abgearbeitet, ich bekomme dann ery(3),

Nach ery(3) folgen dann noch ery(2), ery(1) und ery(0). Erst bei dem letzten Aufruf ist zum ersten mal die Bedingung für den Rücksprung erfüllt. Dieser Rücksprung erfolgt dann an die Stelle nach dem Aufruf von ery(0) und das ist das A() und anschließend yre(0) usw.

 

[infomania383838]

Ich bedanke mich bei euch allen für die Hilfe

Ist die Annahme das wenn man bei ery(0) oder yre(0) angelangt die Rücksprungbedingung erfüllt ist richtig?

Die Darstellung von tommy verwirrt mich als Anfänger leider so sehr, dass ich nicht viel mit anfangen kann. Hätte jemand ansonsten eine Quelle in der solchen rekursiven Aufrufe erklärt werden? Ich habe da leider auch nichts gefunden was mich weiterbringen könnte.

 

[Meniskusschaden]

Ich glaube nicht, dass weitere Erklärungen da viel bringen. Ich würde es lieber einmal als Schreibtischtest Anweisung für Anweisung manuell durcharbeiten und protokollieren. Das ist nicht schwierig, weil du ja einfach nur die Programmzeilen ausführen musst. So siehst du genau, was passiert. Dafür bietet sich dann die Schreibweise von @MoxxiManagarm aus Post #2 an.