Elementare Frage zur Rekursion

freakC++

Moin, moin!
Ich habe das Prinzip der Rekursion verstanden, doch habe ich manchmal Schwierigkeiten zu verstehen, wie eine rekursive Funktion arbeitet. Ich habe mal als Beispiel eine kleine geschrieben:

void rec(int a)
{
	if (a==1) return;
	cout << a << "  " << endl;
	rec(a-1);
	cout << "Dahinter" << "   " << a << endl;
}

int main()
{
	rec(5);
	return 0;
}

Nun versuche ich einfach mal die einzelnen Schritte nachzuvollziehen:

1.) Die Funktion wird aufgerufen, die Fallunterscheidung ist false, weshalb a ausgegeben wird, dann wird die Funktion wieder aufgerufen.

2.) Wenn die Funktion nun wieder aufgerufen wird, wird dann der Anweisungsblock hinter dem Selbstaufruf erstmal nicht ausgeführt (hier also die Ausgabe "Dahinter")?

3.) Die Funktion ruft sich solange auf, bis a 1 ist. Doch wann kommt die Funktion denn hinter den Selbstaufruf? Der Anweisungsblock hinter dem Selbstaufruf wird erst dann ausgeführt, wenn a fünf mal ausgegeben wurde??? Wie kann ich mir das vorstellen? Wann wird was ausgeführt?

Vielen Dank
lg, freakC++

Ein rekursiver Funktionsaufruf ist trotzdem ein Funktionsaufruf und verhält sich nicht anders.
Stell dir einfach vor, die Funktion würde nicht rec(a-1) sondern rec3(), rec2(), usw. aufrufen, dann ist doch klar, wann das nach dem (Selbst)-Aufruf dran kommt.

Tobias Gerg

main()
  rec(5)
    Ausgabe 5
    rec(4)
      Ausgabe 4
      rec(3)
        Ausgabe 3
        rec(2)
          Ausgabe 2
          rec(1)
            return
          Dahinter 2
          return 
        Dahinter 3
        return
      Dahinter 4
      return
    Dahinter 5
    return
  return 0

Du baust einen Callstack auf und wieder ab...

Nanyuki

Bist du sicher, dass du das Prinzip der Rekursion verstanden hast? Wann sollte dahinter denn deiner Meinung nach angezeigt werden?

rec-Aufruf mit a=5:
5 wird ausgegeben
rec wird mit 5-1 aufgerufen:
  rec-Aufruf mit a=4:
  4 wird ausgegeben
  rec wird mit 4-1 aufgerufen:
    rec-Aufruf mit a=3:
    3 wird ausgegeben
    rec wird mit 3-1 aufgerufen:
      rec-Aufruf mit a=2:
      2 wird ausgegeben
      rec wird mit 2-1 aufgerufen:
        rec-Aufruf mit a=1:
        Funktion kehrt zurück
      Dahinter 2 wird ausgegeben
      Funktion kehrt zurück
    Dahinter 3 wird ausgegeben
    Funktion kehrt zurück
  Dahinter 4 wird ausgegeben
  Funktion kehrt zurück
Dahinter 5 wird ausgegeben
Funktion kehrt zurück

SG1

freakC++ schrieb:

1.) Die Funktion wird aufgerufen, die Fallunterscheidung ist false, weshalb a ausgegeben wird, dann wird die Funktion wieder aufgerufen.

Richtig.

2.) Wenn die Funktion nun wieder aufgerufen wird, wird dann der Anweisungsblock hinter dem Selbstaufruf erstmal nicht ausgeführt (hier also die Ausgabe "Dahinter")?

Genau. Ist aber auch nichts verwunderliches. Ist bei einem normalen Funktionsaufruf ja auch so, dass das, was dahinter steht, erstmal nicht ausgeführt wird (sondern erst, wenn der Funktionsaufruf beendet ist.)

3.) Die Funktion ruft sich solange auf, bis a 1 ist. Doch wann kommt die Funktion denn hinter den Selbstaufruf?

Dann wenn die Ausführung von rec(a-1) beendet ist.

Der Anweisungsblock hinter dem Selbstaufruf wird erst dann ausgeführt, wenn a fünf mal ausgegeben wurde???

Ja.

Wie kann ich mir das vorstellen? Wann wird was ausgeführt?

Dein Code hat (ausser der Ausgabe) keine Nebeneffekte, also kannst Du mal versuchen, die einzelnen Aufrufe in die main-Funktion einzusetzen. Vielleicht wird's dann klarer.

freakC++

Hallo,
vielen Dank für die raschen Antworten. Die beiden Grafiken von Nanyuki und Tobias Gerg waren der sehr hilfreich. Nanyuki schrieb, dass " die Funktion zurückkehrt". Genau hier liegt die Frage. Wenn die Fallunterscheidung dann true ist, wird der Befehl return ausgeführt (quasi ein break in der Schleife). Das bedeutet, dass die Funktion unterbrochen wird. Dennoch wird dann erst der Rest ausgeführt, also 5 Mal "Dahinter a" ausgegeben. Wo speichert denn das Computer diese 5 mal. Hätte ich "rec" mit 6 aufgerufen, wann wäre 6 Mal "Dahinter a" ausgegeben.

Könnt ihr mir weiter helfen?

Vielen Dank euch allen
lg, freakC++

Tobias Gerg

Wenn die Fallunterscheidung dann true ist, wird der Befehl return ausgeführt (quasi ein break in der Schleife) ...

Nein nicht unterbrochen, sondern beendet.

Dennoch wird dann erst der Rest ausgeführt, also 5 Mal "Dahinter a" ausgegeben. Wo speichert denn das Computer diese 5 mal. Hätte ich "rec" mit 6 aufgerufen, wann wäre 6 Mal "Dahinter a" ausgegeben.

Könnt ihr mir weiter helfen?

Das Zauberwort heißt Call stack. Und in diesem Zusammenhang die Diskussion hier