Erklärung C-Code Rekursion

Computer: Software & Programmierung C/C++
#1

Hallo.
Ich habe dieses Beispielprogramm von http://de.wikibooks.org/wiki/C-Programmierung:_Rekur… und dazu leider einige Fragen. die beziehen sich eher auf die Fakultät allgemein.

#include

int fakultaet (int);
int main() {
int eingabe;

printf(„Ganze Zahl eingeben: „);
scanf(“%d“,&eingabe);
printf(„Fakultaet der Zahl: %d\n“,fakultaet(eingabe));

return 0;
}

int fakultaet (int a) {
if (a == 0)
return 1;
else
return (a * fakultaet(a-1));
}

Gerade dieses Unterprogramm verstehe ich nicht wirklich.

Angenommen, ich gebe 5 ein, dann wird ja aufgerufen

fakultaet (int a) mit dem Wert a=5

Dann return (5 * fakultaet(5-1));

Das fakultaet(5-1) = fakultaet(4) wird ja jetzt wieder aufgerufen (das Unterprogramm), so lange, bis a == 0 ist.

Was genau bedeutet jetzt das Return 1? Wird damit das Ergebnis an das Hauptprogramm zurückgegeben? Ansonsten versgtehe ich nicht, an welcher Stelle 120 (das Ergebnis von 5!) an das Hauptprogramm bzw. zur Ausgabe zurückgegeben wird. Kann mir das jemand sagen?

#2

Hallo,

int fakultaet (int a) {
if (a == 0)
return 1;
else
return (a * fakultaet(a-1));
}

Gerade dieses Unterprogramm verstehe ich nicht wirklich.

Angenommen, ich gebe 5 ein, dann wird ja aufgerufen

fakultaet (int a) mit dem Wert a=5

Dann return (5 * fakultaet(5-1));

Das fakultaet(5-1) = fakultaet(4) wird ja jetzt wieder
aufgerufen (das Unterprogramm), so lange, bis a == 0 ist.

Was genau bedeutet jetzt das Return 1? Wird damit das Ergebnis
an das Hauptprogramm zurückgegeben?

Nein, an die aufrufende Funktion, und das ist fakultaet(), aufgerufen mit dem Argument 1.
Darin steht dann return 1 * fakultaet(0);, was zu return 1*1 ausgewertet wird.

HTH,
Moritz

#3

Hallo Fragewurm,

int fakultaet (int a) {
if (a == 0)
return 1;
else
return (a * fakultaet(a-1));
}

Gerade dieses Unterprogramm verstehe ich nicht wirklich.

Das ist der rekursive Teil. Also die Funktion ruft sich selber wieder auf:

Angenommen, ich gebe 5 ein, dann wird ja aufgerufen

fakultaet (int a) mit dem Wert a=5

Dann return (5 * fakultaet(5-1));

Hier ist dein Denkfehler !!

Die Klammer wird ja von Innen nach Aussen aufgelöst:

return (5 * fakultaet(5-1));

„5 *“ kann ja erst berechnet werden, wenn die Funktion fakultaet(4) ihr Ergebnis zurückgegeben hat.
Genauso kann aber 4 * fakultaet(3) erste berechnet werden wenn
3 * fakultaet(2) berechnet wurde, was aber das Resultat von
2 * fakultaet(1) voraussetzt …
der Programmablauf ist folglich:

5 * fakultaet(4 * fakultaet(3 * fakultaet(2 * fakultaet(1 * fakultaet(0)))))

Fakultaet(0) liefert als Ergebnis 1

Programmtechnischt ist das ganze Konstrukt genial einfach :wink:
Allerdings werden bei jedem Aufruf die Rücksprung-Adresse und der Übergabeparameter auf dem Stack abgelegt. Was dann, bei einem genügend grossen a zu einem Stacküberlauf führt.
Bei einem System mit 16 Bit-Adressbreite und 16 Bit für einen Integer, sind das für jeden Aufruf 4 Byte. Somit würde bei a = 16384 der ganze verfügbare Adressraum nur für den Stack zum Aufruf dieser Rekursion benötigt.

MfG Peter(TOO)