Entrekursivierung

Entrekursivierung bezeichnet in der Informatik das Umwandeln einer rekursiven Funktion in eine iterative Funktion.

Rekursionen sind eine Technik, die häufig in der Informatik eingesetzt werden, um eine Funktion durch sich selbst zu definieren. Dafür löst die rekursive Funktion das gegebene Problem zuerst teilweise oder teilt es in mehrere Teilprobleme auf und ruft sich selbst dann mit diesen neuen Teilproblemen auf. Dies geschieht so lange, bis das Problem vollständig gelöst ist oder die Lösung in triviale Einzelteile zerlegt ist.

Rekursive Lösungen sind oft eleganter und einfacher zu finden sowie einfacher auf ihre Korrektheit zu prüfen (z. B. mittels Mathematischer Induktion) als iterative Funktionen, sind aber aufgrund der vielen Funktionsaufrufe je nach verwendeter Programmiersprache weniger performant, weswegen es sich bei Performance-kritischen Programmteilen oft auszahlt, eine rekursive Funktion zu entrekursivieren. Da Rekursionen und Iterative Funktionen gleich mächtig sind, gibt es für jede Rekursion ein iteratives Äquivalent.

Lineare Rekursion auflösen

Lineare Rekursionen sind Rekursionen, bei denen es pro Rekursionsschritt maximal einen Rekursionsaufruf gibt. Die Berechnung läuft hierbei entlang einer Kette von Aufrufen. Lineare Rekursionen lassen sich sehr leicht auflösen. Als Beispiel hierzu eine rekursive Funktion, die die Fakultät einer Zahl berechnet.

int fac(int x) {
	if (x = 0) {
		return 1;
	} else {
		return x * fac(x - 1);
	}
}

Das Erste, was hier notwendig ist, ist die getrennten Return-Werte auf einen Return-Wert zu reduzieren:

int fac(int x) {
	int value;
	if (x = 0) {
		value = 1;
	} else {
		value = x * fac(x - 1);
	}
	return value;
}

Als Letztes wird der Return-Befehl durch einen Akkumulator und die Rekursion durch eine Schleife ersetzt:

int fac(int x) {
	int accumulator = 1;
	bool running = true;
	while (running) {
		int value;
		if (x = 0) {
			value = 1;
			running = false; //Hier endet die Rekursionskette
					 //im ursprünglichen Algorithmus.
					 //Äquivalent zu return(1);
		} else {
			value = x;
			x = x-1;	 //Hier geht die Rekursionskette weiter.
			running = true;	 //Äquivalent zu return x*fac(x-1);
		}
		accumulator = accumulator * value;
	}
	return accumulator;
}

Diese Funktion lässt sich dann noch optimieren, indem unnötige Zuweisungen ausgelassen werden, die durch die Umwandlung entstanden sind.