C-Programmierung
Rekursionsbeispiel
← Rekursion | ● | Iterationsbeispiel →
Ein einfaches Rekursionsbeispiel anhand der rekursiven Definition der Fakultät $n!=factorial(n)$:
$ factorial(n) = n \cdot factorial(n-1) \quad \forall n>1 $
$ factorial(1) = 1 $
$ factorial(1) = 1 $
Dies entspricht 1:1 der folgenden C-Funktion:
unsigned int factorial(unsigned int n)
{
if (n>1) return(n * factorial(n-1));
else return(1);
}
{
if (n>1) return(n * factorial(n-1));
else return(1);
}
Ablauf von factorial(4):
factorial(4) = 4 * factorial(4-1) = 4 * (3 * factorial(3-1)) = 4 * (3 * (2 * factorial(2-1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24
Bei jedem rekursiven Aufruf werden neue Instanzen von n mit den Werten 4, 3, 2, 1 angelegt.
Tipp: Nachverfolgen der rekursiven Funktionsaufrufe im Debugger (Step by Step)
← Rekursion | ● | Iterationsbeispiel →