Entrekursivierung

Grundidee

Entrekursivierung bezeichnet in der Informatik das Umwandeln einer rekursiven Funktion in eine iterative Funktion. Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft, um ein Problem zu lösen. Sie löst das Problem dabei entweder teilweise oder teilt es in kleinere Teilprobleme auf und ruft sich mit diesen Teilproblemen erneut auf. Dieser Vorgang endet, wenn das Problem vollständig gelöst ist oder nur noch triviale Einzelfälle übrig sind.

Entrekursivierung ist wichtig, weil rekursive Lösungen oft elegant, leicht zu finden und gut auf Korrektheit zu prüfen sind, zum Beispiel mit Mathematischer Induktion. Gleichzeitig können sie wegen vieler Funktionsaufrufe je nach Programmiersprache weniger performant sein. In performance-kritischen Programmteilen kann es sich deshalb lohnen, eine rekursive Funktion in eine iterative umzuwandeln. Da Rekursionen und iterative Funktionen gleich mächtig sind, gibt es für jede Rekursion ein iteratives Äquivalent.

Lineare Rekursion

Eine lineare Rekursion ist eine Rekursion, bei der es pro Rekursionsschritt höchstens einen Rekursionsaufruf gibt. Die Berechnung verläuft dabei entlang einer Kette von Aufrufen. Solche Rekursionen lassen sich besonders leicht auflösen.

Das Beispiel im Artikel ist eine Funktion zur Berechnung der Fakultät einer Zahl. Die Fakultät wird rekursiv so berechnet: Wenn x = 0 gilt, liefert die Funktion 1 zurück. Andernfalls liefert sie x * fac(x - 1). Dadurch ruft sich die Funktion immer wieder mit einer um 1 kleineren Zahl auf, bis der Fall x = 0 erreicht ist.

Umwandlungsschritte

Beim Auflösen der linearen Rekursion wird zuerst die Struktur der Rückgaben verändert. Die getrennten return-Anweisungen werden auf einen einzigen Rückgabewert reduziert. Dazu wird eine Variable value eingeführt: Im Fall x = 0 wird value = 1 gesetzt, sonst value = x * fac(x - 1). Am Ende gibt es nur noch return value.

Danach werden der rekursive Aufruf und der return-Befehl durch eine Schleife und einen Akkumulator ersetzt. Ein Akkumulator ist eine Variable, die Zwischenergebnisse sammelt. Im Beispiel startet accumulator mit 1. Solange die Berechnung läuft, wird geprüft, ob x = 0 gilt. Wenn ja, endet die ursprüngliche Rekursionskette; value wird auf 1 gesetzt und running auf false. Wenn nein, wird value auf x gesetzt, x wird zu x - 1 verändert, und die Schleife läuft weiter. In jedem Durchlauf wird accumulator = accumulator * value ausgeführt. Am Ende gibt die iterative Funktion accumulator zurück.

Nach der Umwandlung kann die Funktion noch optimiert werden, indem unnötige Zuweisungen entfernt werden, die nur durch die mechanische Umformung entstanden sind.