Rekursion

Rekursiv oder Iterativ, das ist hier die Frage!

Im nachfolgenden Artikel wird das Thema Rekursion in Java erläutert. Rekursion wird für viele Programmiereinsteiger am Anfang eine Königsdisziplin sein, deren Funktionsweise nicht ganz einfach nachzuvollziehen ist und so selbst fortgeschrittene Programmierer öfters vor Hürden stellen wird. Dennoch ist es wichtig die Rekursion zu verstehen und auch anwenden zu können, da man mit ihr in einigen Problemfällen zu sehr eleganten Lösungen kommt.

Konkret versteht man unter Rekursion den Aufruf einer Funktion durch sich selbst. Bei jedem rekursiven Aufruf wird dabei eine neue Instanz der jeweiligen Methode gestartet. Grundsätzlich folgt die Rekursion dem Grundprinzip: „divide et impera“ („Teile und Herrsche“). Bei diesem Prinzip wird das Problem in mehrere kleinere Teilprobleme zerlegt. Diese Teilprobleme werden gelöst und anschließend werden die Teillösungen wieder zu einer Gesamtlösung vereint.

Die Rekursion steht der Iteration gegenüber. Viele Probleme können entweder iterativ oder aber auch rekursiv gelöst werden. Oft ist die rekursive Lösung zwar kompakter/kürzer als die iterativen Varianten, dafür ist sie aber auch oft langsamer und der Speicheraufwand ist höher.

Das Standard-Beispiel mit dem man sowohl eine rekursive wie auch iterative Lösung gegenüber stellen kann, ist die Fakultätsberechnung (z.B. 5! = 1 * 2 * 3 * 4 * 5)

Iterativ, also mit Schleifen lässt sich die Fakultät folgendermaßen bestimmen:

static int fakultaetIterativ(int n) {
		int ergebnis = 1;
		for (int i = 1; i <= n; i++) {
			ergebnis = ergebnis * i;
		}
		return ergebnis;
	}

Die Berechnung der Fakultät mit Rekursion sieht hingegen so aus:

static int fakultaetRekursiv(int n) {
		if (n <= 1)
			return 1;
		else
			return fakultaetRekursiv(n - 1) * n;
	}

Bei beiden Varianten wird als Ergebnis "120" zurückgegeben, wenn man für n=5 eingibt.