C-Programmierung: Rekursion
Aus Wikibooks
[Bearbeiten] Rekursion
Eine Funktion, die sich selbst aufruft, wird als rekursive Funktion bezeichnet. Den Aufruf selbst nennt man Rekursion. Als Beispiel dient die 
Fakultäts-Funktion n!, die sich rekursiv als n(n-1)! definieren lässt (wobei 0! = 1).
Hier ein Beispiel dazu in C:
-
#include <stdio.h> -
-
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)); -
}
[Bearbeiten] Beseitigung der Rekursion
Rekursive Funktionen sind in der Regel leichter lesbar als ihre iterativen Gegenstücke. Sie haben aber den Nachteil, dass für jeden Funktionsaufruf verhältnismäßig hohe Kosten anfallen. Eine effiziente Programmierung in C erfordert also die Beseitigung jeglicher Rekursion. Am oben gewählten Beispiel der Fakultät könnte eine rekursionsfreie Variante wie folgt definiert werden:
int fak_iter(int n) { int i, fak; for (i=1, fak=1; i<=n; i++) fak *= i; return fak; }
Diese Funktion liefert genau die gleichen Ergebnisse wie obige, allerdings wurde die Rekursion durch eine Iteration ersetzt. Offensichtlich kommt es innerhalb der Funktion zu keinem weiteren Aufruf, was die Laufzeit des Algorithmus erheblich verkürzen sollte. Komplexere Algorithmen - etwa Quicksort - können nicht so einfach iterativ implementiert werden. Das liegt an der Art der Rekursion, die es bei Quicksort notwendig macht, einen Stack für die Zwischenergebnisse zu verwenden. Eine so optimierte Variante kann allerdings zu einer Laufzeitverbesserung von 25-30% führen.
[Bearbeiten] Weitere Beispiele für Rekursion
Die Potenzfunktion "y = x hoch n" soll berechnet werden:
-
#include <stdio.h> -
-
int potenz(int x, int n)
-
{ -
if (n>0)
-
return (x*potenz(x,--n)); /* rekursiver Aufruf */ -
else -
return (1); -
} -
-
int main(void)
-
{ -
int x;
-
int n;
-
int wert;
-
-
printf("\nGib x ein: ");
-
scanf("%d",&x);
-
printf("\nGib n ein: ");
-
scanf("%d",&n);
-
-
if(n<0)
-
{ -
printf("Exponent muss positiv sein!\n"); -
return 1; -
} -
else -
{ -
wert=potenz(x,n); -
printf("Funktionswert: %d",wert); -
return 0; -
} -
}
Multiplizieren von zwei Zahlen als Ausschnitt:
int multiply(int a, int b) { if (b==0) return 0; return a + multiply(a,b-1); }
