Speicherbedarf von Klasse
-
Auch bei Rekursion belegt eine Funktion nicht mehr platz als sonst. Denn die Funktion existiert ja nur einmal, egal wie oft du sie aufrufst... es sei denn du willst veruschen eine rekursion zu inlinen... das wäre aber ein langwieriges unterfangen
-
Shade Of Mine schrieb:
es sei denn du willst veruschen eine rekursion zu inlinen... das wäre aber ein langwieriges unterfangen
Wo wir beim Thema sind: Gibt es Optimierer, die das können? Gesetzt den Fall, es handelt sich um eine endrekursive Funktion, die man als Iteration übersetzen kann.
-
Wenn es dann als Iteration dasteht brauchste ja nichts mehr inlinen. Und ei Funktion selbst kann dann natürlich auch bequem geinlined werden... ist ja kein rekursiver Aufruf mehr drin.
-
Jester schrieb:
Wenn es dann als Iteration dasteht brauchste ja nichts mehr inlinen. Und ei Funktion selbst kann dann natürlich auch bequem geinlined werden... ist ja kein rekursiver Aufruf mehr drin.
Klar, aber gibt es Compiler, die das automatisch können? Also Endrekursion erkennen und inlinen?
-
Konrad Rudolph schrieb:
Shade Of Mine schrieb:
es sei denn du willst veruschen eine rekursion zu inlinen... das wäre aber ein langwieriges unterfangen
Wo wir beim Thema sind: Gibt es Optimierer, die das können? Gesetzt den Fall, es handelt sich um eine endrekursive Funktion, die man als Iteration übersetzen kann.
Was soll "endrekursive Funktion" heißen? Daß eine Rekursion nach einer Weile abbricht?
Selbst dann kann man die Abbruchbedingung erst zur Laufzeit feststellen:
[cpp]
inline int fak (int val)
{
if (val == 1)
return (1);
return (fak (val - 1) * val);
}
[/cpp]Wie sollte ein Compiler das umsetzen (wenn die Funktion nicht mit einem konstanten Wert aufgerufen wird, ist val bzw. die Häufigkeit der Iteration zur Kompilierzeit nicht bekannt)?
Außerdem: für konstante Werte gibt es rekursive Templates.
Moritz
-
audacia schrieb:
Was soll "endrekursive Funktion" heißen?
Das kann man im Web leicht herausfinden.
-
audacia schrieb:
Konrad Rudolph schrieb:
Shade Of Mine schrieb:
es sei denn du willst veruschen eine rekursion zu inlinen... das wäre aber ein langwieriges unterfangen
Wo wir beim Thema sind: Gibt es Optimierer, die das können? Gesetzt den Fall, es handelt sich um eine endrekursive Funktion, die man als Iteration übersetzen kann.
Was soll "endrekursive Funktion" heißen? Daß eine Rekursion nach einer Weile abbricht?
Nö, sondern dass sie am die letzte Operation in einer Rekursion ist. Beispiel:
int sum(int n, int accu = 0) { if (n == 0) return accu; return sum(n - 1, accu + n); }Wenn man das als Baum schreibt, ist die Rekursion der letzte Funktionsaufruf. In Assembler wäre das dann so, dass direkt hinter dem 'call'-Statement ein 'ret'-Statement steht. Daher kann man das 'call'-Statement einfach durch ein 'jmp'-Statement ersetzen und 'ret' weglassen. Man spart sich, die Stack-Frame für jeden rekursiven Aufruf zu sichern.
-
Bashar schrieb:
audacia schrieb:
Was soll "endrekursive Funktion" heißen?
Das kann man im Web leicht herausfinden.
Stimmt, hab soeben danach gegoogled, leider zu spät drangedacht
Wenn man das als Baum schreibt, ist die Rekursion der letzte Funktionsaufruf. In Assembler wäre das dann so, dass direkt hinter dem 'call'-Statement ein 'ret'-Statement steht. Daher kann man das 'call'-Statement einfach durch ein 'jmp'-Statement ersetzen und 'ret' weglassen. Man spart sich, die Stack-Frame für jeden rekursiven Aufruf zu sichern.
Gute Idee, doch es würde mich wundern, wenn ein Compiler das könnte (Der Borland-Compiler kann es jedenfalls nicht, ich hab's gerade ausprobiert).
Außerdem kann man eine solche Funktion ja problemlos selbst in Assembler realisieren.
Moritz
-
audacia schrieb:
doch es würde mich wundern, wenn ein Compiler das könnte
mich nicht. eine endrekursive Funktion läßt sich kanonisch in eine iterative überführen.
-
Nun ist aber Endrekursion nicht gerade eine verbreitete Programmiertechnik in imperativen Sprachen. Welchen Nutzen hätte es für einen Compilerhersteller, den Aufwand zu investieren, wenn es effektiv niemandem nutzt, weil 99,99% der User sowieso jede Iteration als Schleife schreiben?