Hallo
Ich habe da mal ein Frage und zwar geht es um die Rekursion. Könnte mir ja mal jemand auf die Sprünge helfen und mir erklären, was das genau auf sich hat und wie man das in C unsetzen kann.
Gruß
kingmar
Hallo kingmar,
Ich habe da mal ein Frage und zwar geht es um die Rekursion.
Könnte mir ja mal jemand auf die Sprünge helfen und mir
erklären, was das genau auf sich hat und wie man das in C
unsetzen kann.
Rekursion bedeutet, dass sich eine Funktion selbst wieder aufruft. In der Praxis kann es auch sein, dass eine Unterfunktion eine übergeordnete Funktion aufruft welche dann wieder …
Das eigentliche Problem ist, dass bei jedem Aufruf neuer Platz auf dem Stack belegt wird und dann irgend wann der Stack aus allen Nähten platzt. Jedes Problem welches rekursiv gelöst werden kann, kann auch als Schleife programmiert werden. Normalerweise sollte man Rekursionen meiden.
Hier mal ein kleines unsinniges Programm zur Verdeutlichung:
Rekursiv:
int rest(int zahl, int teiler)
{
if ( zahl rest(zahl-teiler, teiler);
}
Schlaufe:
int rest(int zahl, int teiler)
{
while (zahl \>= teiler)
{
zahl = zahl-teiler;
}
return zahl;
}
Das Problem der rekursiven Variante ist z.B. wenn man für zahl = 32’000 und teiler = 1 einsetzt. Diese Funktion wird dann 32’001 mal aufgerufen. Bei einem 32-Bit Prozessor muss, im besten Fall, nur die Rückspung-Adresse auf dem Stack abgelegt werden, das sind also 4-Byte. Somit muss der Stack mindestens 128 KB gross sein.
Mit ein paar gesicherten CPU-Registern und einigen lokalen Variablen hast du schnell einen enorm grossen Stack beisammen.
Wie du siehst ist das Umsetzen nicht das Problem, meist aber die Vermeidung.
MfG Peter(TOO)
Hallo,
hier noch ein schöner Überblick über dieses Thema:
http://www.pronix.de/C/standard_C/ckurs/ckurs131.html
Allg.: http://www.pronix.de/C/index.shtml
Gruß, olli
Scherz am Rande
Um Rekursion zu verstehen, muß man erst Rekursion verstehen.
Ok, nicht sehr hilfreich, aber das trifft es ziemlich genau.
Gruß
Moriarty
Hallo,
Jedes Problem welches rekursiv gelöst werden kann, kann auch als Schleife programmiert werden.
Iterativ ja, z.B. indem man den Stapel selbst verwaltet.
Normalerweise sollte man Rekursionen meiden.
Das gilt sicher für solche Formen der Rekursion, die sich leicht „entfalten“ lassen. Ansonsten sind die iterativen Lsg. bedeutend schwerer zu lesen und bei vernünftiger Programmiersprache auch ineffizienter.
Gruss
Enno