Recursion

Rekursion

Rekursion ist die Technik, einen Funktionsaufruf selbst durchzuführen. Diese Technik bietet eine Möglichkeit, komplizierte Probleme in einfache Probleme zu zerlegen, die leichter zu lösen sind.

Rekursion kann etwas schwierig zu verstehen sein. Der beste Weg, herauszufinden, wie sie funktioniert, besteht darin, damit zu experimentieren.

Rekursionsbeispiel

Das Addieren zweier Zahlen ist einfach, das Addieren eines Zahlenbereichs ist jedoch komplizierter. Im folgenden Beispiel wird Rekursion verwendet, um einen Zahlenbereich zu addieren, indem dieser in die einfache Aufgabe des Addierens zweier Zahlen zerlegt wird:

Beispiel

int sum(int k);

int main() {
  int result = sum(10);
  printf("%d", result);
  return 0;
}

int sum(int k) {
  if (k > 0) {
    return k + sum(k - 1);
  } else {
    return 0;
  }
}

Beispiel erklärt

Wenn die Funktion sum() aufgerufen wird, addiert sie den Parameter k zur Summe aller Zahlen kleiner als k und gibt das Ergebnis zurück. Wenn k 0 wird, gibt die Funktion einfach 0 zurück. Beim Ausführen befolgt das Programm diese Schritte:

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

Da die Funktion sich nicht selbst aufruft, wenn k 0 ist, stoppt das Programm dort und gibt das Ergebnis zurück.

Der Entwickler sollte bei der Rekursion sehr vorsichtig sein, da es leicht passieren kann, dass er eine Funktion schreibt, die nie beendet wird oder die übermäßig viel Speicher oder Prozessorleistung verbraucht. Wenn sie jedoch richtig geschrieben wird, kann Rekursion ein sehr effizienter und mathematisch eleganter Ansatz für die Programmierung sein.