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 lassen sind oft eleganter und einfacher zu finden sowie einfacher auf ihre Korrektheit zu prüfen (z.B. mittels Mathematischer Induktion) als iterative Funktionen,^[1] sind aber aufgrund der vielen Funktionsaufrufe je nach verwendeter Programmiersprache weniger performant,^[2] 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.^[3]

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. ^[4] Als Beispiel nehmen wir 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 ersetzen wir den Return-Befehl mit einem Akkumulator und die Rekursion mit einer Schleife:

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.

1. ↑ Algorithmen und Datenstrukturen - G. Pomberger und H. Dobler. Abgerufen am 17. Juni 2014.
2. ↑ Algorithmen und Datenstrukturen 04. Website der Technischen Fakultät der Universität Erlangen. Abgerufen am 17. Juni 2014.
3. ↑ Algorithmen und Datenstrukturen 06 Entrekursivierung. Website des Instituts für Wirtschaftsinformatik und Software Engineering der Universität Linz. Abgerufen am 17. Juni 2014.
4. ↑ Programmieren und Beweisen - H. Peter Gumm. Abgerufen am 17. Juni 2014.