Rekursionsfrage

icarus2

Es sieht aber intern nicht so aus wie du beschrieben hast.

Ja, es gibt nur den letzen Rückgabewert b. Aber dieser muss durch alle Rekursionsstufen zurückgegeben (hochgereicht) werden.
return ggT(a,tmp); hat immer den Wert b.

CStoll

freakC++ schrieb:

Aber es gibt doch hier nur einen Rückgabewert, nämlich das letzte "b".

Ja, aber dieses ist etwas ganz anderes als das b, was vom Hauptprogramm reingekommen ist - bei jedem Aufruf der Funktion ggT() wird ein weiteres Stück vom Stack reserviert und dort eine eigene Version von a, b und tmp untergebracht (zusammen mit einigen Verwaltungs-Informationen, um beim Funktionsende alles wieder aufräumen zu können) - womöglich auf für eine temporäre Variable, die den Rückgabewert des rekursiven Aufrufs aufnehmen kann. Beim return wird der dort genannte Wert in den Speicherbereich des Aufrufers geschrieben und kann anschließend weiterverarbeitet werden (daß sich diese Weiterverarbeitung hier auf eine Rückgabe beschränkt, hat darauf keinen Einfluß).

volkard

@freakC++: Bitte schreibe am Ende, wenn das Problem gelöst würde, wer von den Helfern daran den größten Einfluß hatte.

icarus2

volkard schrieb:

@freakC++: Bitte schreibe am Ende, wenn das Problem gelöst würde, wer von den Helfern daran den größten Einfluß hatte.

Bin ja schon ruhig.

Jockelx

volkard schrieb:

@freakC++: Bitte schreibe am Ende, wenn das Problem gelöst würde, wer von den Helfern daran den größten Einfluß hatte.

Ich, da ich als einziger im letzen Thread schon erkannt habe, wo sein Denkfehler ist und ein rekursiver Funktionsaufruf nichts besonderes ist.
Stattdessen wurde sich aber lieber über Kompileroptimierungsmöglichkeiten von Rekursionen unterhalten.
:p

freakC++

CStoll schrieb:

Ja, aber dieses ist etwas ganz anderes als das b, was vom Hauptprogramm reingekommen ist - bei jedem Aufruf der Funktion ggT() wird ein weiteres Stück vom Stack reserviert und dort eine eigene Version von a, b und tmp untergebracht (zusammen mit einigen Verwaltungs-Informationen, um beim Funktionsende alles wieder aufräumen zu können) - womöglich auf für eine temporäre Variable, die den Rückgabewert des rekursiven Aufrufs aufnehmen kann. Beim return wird der dort genannte Wert in den Speicherbereich des Aufrufers geschrieben und kann anschließend weiterverarbeitet werden (daß sich diese Weiterverarbeitung hier auf eine Rückgabe beschränkt, hat darauf keinen Einfluß).

Ahh..danke! Es geht als vor allem um das Aufräumen des Stacks, das ohne das return vor dem Selbstaufruf nicht funktionieren würde. Habe ich das richtig verstanden?

volkard schrieb:

@freakC++: Bitte schreibe am Ende, wenn das Problem gelöst würde, wer von den Helfern daran den größten Einfluß hatte.

Das verstehe ich wiederum nicht. Habe ich was falsch gemacht? Was meinst Du?

Bashar

freakC++ schrieb:

Ahh..danke! Es geht als vor allem um das Aufräumen des Stacks, das ohne das return vor dem Selbstaufruf nicht funktionieren würde. Habe ich das richtig verstanden?

Nein, der Stack räumt sich auch ohne return auf. Es geht um das zurückgeben des Wertes.

Stell dir vor, wir implementieren mult nicht-rekursiv, eher pseudo-rekursiv:

int mult2(int a, int b)
{
  if(b == 0)
    return b;
  throw "maximum recursion depth exceeded";
} 

int mult1(int a, int b)
{
  if(b == 0)
    return b;
  return a+mult2(a,b-1);
} 

int mult(int a, int b)
{
  if(b == 0)
    return b;
  return a+mult1(a,b-1);
}

Das funktioniert genauso wie das rekursive mult, nur greift mult auf eine Funktion mult1 zurück, die wiederum auf mult2 zurückgreift. An der Stelle hab ich dann mal abgebrochen, man kann halt nur maximal mit 2 multiplizieren.

Jetzt frag ich dich: Macht es ohne return Sinn?

CStoll

freakC++ schrieb:

CStoll schrieb:

Ja, aber dieses ist etwas ganz anderes als das b, was vom Hauptprogramm reingekommen ist - bei jedem Aufruf der Funktion ggT() wird ein weiteres Stück vom Stack reserviert und dort eine eigene Version von a, b und tmp untergebracht (zusammen mit einigen Verwaltungs-Informationen, um beim Funktionsende alles wieder aufräumen zu können) - womöglich auf für eine temporäre Variable, die den Rückgabewert des rekursiven Aufrufs aufnehmen kann. Beim return wird der dort genannte Wert in den Speicherbereich des Aufrufers geschrieben und kann anschließend weiterverarbeitet werden (daß sich diese Weiterverarbeitung hier auf eine Rückgabe beschränkt, hat darauf keinen Einfluß).

Ahh..danke! Es geht als vor allem um das Aufräumen des Stacks, das ohne das return vor dem Selbstaufruf nicht funktionieren würde. Habe ich das richtig verstanden?

Nein, der Compiler wird am Ende der Funktion versuchen, eine eigene return-Anweisung zu ergänzen, um den Programmfluß wieder um Aufrufer zurückzuleiten (die Alternative wäre schmlimmer). Allerdings ist afaik nicht definiert, welche Wert er dann an den Aufrufer zurückgeben wird - dadurch bekommst du dann höchstwahrscheinlich Müll im Hauptprogramm geliefert.
Allerdings sollte dein Compiler dich auch warnen, wenn er zu diesem Schritt gezwungen ist.

Ich versuchs auch mal zu erklären...

int Endlos(int a) {
return Endlos(a)
}

Ich hoffe es ist klar, dass das eine Endlosschleife bildet (die irgendwann absürzt).
Um rauszufinden was er da genau returnen soll, muss er "int Endlos(int a)" auswerten, um das auszuwerten muss er "int Endlos(int a)" auswerten, um das ...

Man braucht also für eine Rekursion immer eine Abbruchbedingung, etwas was sagt "Ich bin hier fertig", etwas was eben nicht erneut die Funktion aufruft und die Rekursion fortsetzt. Deswegen braucht eine rekursive Funktion prinzipiell immer 2-mal return. Einmal zum weitermachen, und einmal zum aufhören.
Man hört normalerweise auf wenn man sein Ergebnis hat, und das ist in beiden deiner Beispiele "b" - das Ergebnis, das zurückgegeben wird.

CStoll

kleiner Troll schrieb:

Ich versuchs auch mal zu erklären...

Netter Vortrag, aber ein wenig am Thema vorbei. Außerdem ist es weder notwendig noch ausreichend, in einer rekursiven Funktion genau zwei return zu haben.

freakC++

Danke für die Antworten. Ich denke, ich habe es verstanden. Wenn ich das return nicht schreiben würde, dann gäbe es für meisten Aufrufe keinen Rückgabetyp und das wäre gegen den Sinn einer Funktion.

lg, freakC++