C-Programmierung: Rekursion

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 a)
{
  if (a == 0)
    return 1;
  else
    return (a * fakultaet(a-1));
}

int main()
{
  int eingabe; 

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

  return 0;
}

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 die 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.

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\n",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);
}