Konrad-Adenauer-Gymnasium Langenfeld

Informatik Grundkurs Q1

Rekursive Funktionen

Unter einer rekursiven Funktion versteht man eine Methode, die sich selbst aufruft. Damit das nicht endlos weiter geht, muss über eine Abbruchbedingung dafür gesorgt werden, dass irgendwann die Rekursion endet.

Eine Rekursion entspricht also vom Grundprinzip einer Schleife. Je nachdem, an welcher Stelle die Abbruchbedingung überprüft wird, mit Anfangs- oder Endebedinung.

Der Gegenbegriff der Informatik zur Rekursion ist die Iteration (oder iterative Funktion), bei der in einer Schleife durch wiederholte (iterierte) Anwendung das Ergebnis berechnet wird.

Als Beispiel soll hier die Berechnung der Fakultät n! dienen.

n! = 1 * 2 * 3 * ... * (n-1) * n

also z.B. 5! = 1 * 2 *3 * 4 * 5 = 120.

iterative Lösung:

Es wird ausgehend vom Wert 1 in jedem Schleifendurchlauf der nachfolgende Wert dazu addiert bis n erreicht ist.

long fakiter(long n)
{
  long fak=1;
  for(long i=1;i<=n;i++)
    fak=fak*i;
  return fak;
}

Die Komplettlösung (gibt es später)

rekursive Lösung:

Es gilt n! = n * (n-1)!

Damit kann die Berechnung von n! auf die Berechnung von (n-1)! zurückgeführt werden (Rekursion). Sobald 1! erreicht ist, muss abgebrochen werden.

long fakRek(long n)
{
  if (n!=1)
    return n*fakRek(n-1);
  else
    return 1;
}