Grundlagen: Was ist Endrekursion?

Posted by in clojure, funktionale Programmierung, funktionales Programmieren, JavaScript

Rekursion ist ein mächtiges Konzept in der Programmierung, bei dem eine Funktion sich selbst aufruft. In meiner Studienzeit gab es einen witzigen Spruch:

Informatikerhandbuch – Rekursion:
Siehe Rekursion

Dieser beschreibt treffend die Idee, eine Aufgabe mit einer sich selbst aufrufenden Funktion zu lösen.

Ein Beispiel

Wir starten mit einem kleinen Beispiel, das man sofort findet, wenn man nach Rekursion sucht. Der Fibonacchi-Folge (JavaScript):

Leider gibt es mit dieser Implementierung ein Problem. Der Speicherverbrauch dieser Funktion wächst bei großen n stark an. Schuld ist, dass für jeden Aufruf von fib(n) neuer Speicher belegt wird. Das liegt zum einen daran, dass die Berechnung erst zum Stillstand kommt, wenn n <= 1 ist. Zum Anderen, dass der Aufruf von fib(n-1) und fib(n-2) nicht die letzte Berechnung ist, die in dieser Funktion statt findet. Es ist nämlich die Summe dieser beiden Aufrufe. Bei großen n ergibt sich also die folgende Aufrufkette (Achtung: Schematische Darstellung):

fib(5) >
–fib(4) + fib(3) >
—-(fib(3) + fib(2)) + (fib(2) + fib(1)) >
——(fib(2) + fib(1))

Jede neue Treppenstufe belegt Platz im Speicher und erst zum Ende der Berechnung wird dieser wieder frei gegeben. Bei n >= 45 beschwert sich schon mein Browser, dass die Berechnung zu lange dauert.

Die Lösung: Endrekursion

Viele Programmiersprachen unterstützen ein Konzept namens Endrekursion und optimieren nicht endrekursive Rekursionen. Dabei wird das Speicherproblem umgangen, indem die Berechnung in eine iterative Variante vom Compiler umgeschrieben wird (Das geht immer!). Das erreicht man in unserem Fall dadurch, dass der letzte Ausdruck nach return keine Berechnungen mehr enthält, sondern nur den rekursiven Aufruf der Funktion.

Es ergibt sich daraus der folgende Aufrufkette, die keinen zusätzlichen Speicher belegt.

fib(0, 1, 5) > fib(1, 1, 4) > fib(2, 1, 3) > fib(3, 2, 2) > fib(5, 3, 2) > fib(8, 5, 1)

Diese Variante läuft selbst für sehr große n effizient in meinem Browser 🙂

Eine kleine JSBin habe ich auch noch vorbereitet.

Fazit

Das Konzept der Endrekursion ist im ersten Moment schwierig zu verstehen. Programmiert man jedoch hauptsächlich funktional ist ein Verständnis dafür unabdingbar, um effizienten Code zu schreiben.

In einigen Sprachen (ECMAScript 2015) optimiert der Compiler nicht endrekursive Rekursionen automatisch. In anderen wiederum nicht (Clojure: Schlüsselwort benötigt). Es gibt eine kleine Übersicht auf Wikipedia.

Weiterführende Links:
Endrekursion auf Wikipedia
CPS – Continuation passing style

Gibt es noch eine bessere Erklärung? Schreibt in den Kommentaren dazu!