Entrekursivierung
# 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.

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

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

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

