Stefan Röttger C-Programmierung/Rekursionsbeispiel

C-Programmierung

Rekursionsbeispiel

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$

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);
}

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)