Engineering Kiosk Episode #173 Rekursion: Das Ende ist nah!

#173 Rekursion: Das Ende ist nah!

software-engineering
Copy Link
Diese Episode in deiner Podcast-App hören...
Engineering Kiosk #173 Rekursion: Das Ende ist nah! bei Apple Podcasts Apple
Engineering Kiosk #173 Rekursion: Das Ende ist nah! auf Spotify Spotify
Engineering Kiosk #173 Rekursion: Das Ende ist nah! auf Amazon Music Amazon
Engineering Kiosk #173 Rekursion: Das Ende ist nah! auf Deezer deezer
Engineering Kiosk #173 Rekursion: Das Ende ist nah! auf YouTube YouTube

Shownotes / Worum geht's?

Was ist Tail Recursion bzw. eine Endrekursion?

Im Engineering Kiosk Adventskalender 2024 sprechen befreundete Podcaster⋅innen und wir selbst, Andy und Wolfi, jeden Tag kurz & knackig innerhalb von wenigen Minuten über ein interessantes Tech-Thema.

Unsere aktuellen Werbepartner findest du auf https://engineeringkiosk.dev/partners

Das schnelle Feedback zur Episode:

👍 (top) 👎 (geht so)

Feedback

Sprungmarken

(00:00:00) Tail Recursion / Endrekursion

Hosts

Feedback

 

Transkript

Das Transkript wurde automatisiert per Speech-to-Text erstellt und kann daher Fehler enthalten.

Andy Grunwald (00:00:09 - 00:00:56) Teilen

Willkommen im Engineering Kiosk Adventskalender. Wir sind bei Türchen 22 und schreiben den vierten Advent. Ich hoffe, dass ihr bereits alle Geschenke beisammen habt. Geschenke sind natürlich eine zusätzliche finanzielle Belastung, deswegen habe ich meinen Chef vor kurzem nach einer Gehaltserhöhung gefragt, um das Ganze überhaupt stemmen zu können. Ob ich diese Exception fangen konnte, werden meine Liebsten dann an Heiligabend sehen. Bevor es aber an leckeres Essen, Geschenken und den Schnaps danach geht, kümmert sich Wolfgang noch um etwas algorithmische Bildung. Es geht um Stacks, es geht um Overflows und um Rekursion. Also für die nächsten 10 Minuten aufpassen und Dr. Wolfgang Gassler lauschen. Zweitausendein, los geht's.

Wolfi Gassler (00:00:56 - 00:11:27) Teilen

Das wird jetzt vielleicht so eine der alte Mann erzählt vom Krieg Geschichte, aber ihr müsst euch vorstellen, früher, früher, wie es noch kein ChatGPT gab oder den Copilot, da musste man, wenn man Fehler hat, noch auf eine Webseite im Internet gehen und manuell die Infos raussuchen. Die bekannteste von diesen Webseiten, die hat sich Stack Overflow genannt. Und da sind wir eigentlich schon beim Problem, dem Stack Overflow Problem. Und genau das wollen wir heute eigentlich auch ein bisschen mit besprechen, denn es geht um die Rekursion und zwar um eine ganz spezielle Version der Rekursion, die Entrekursion oder Tail Recursion auch genannt. Kleiner Exkurs, was ist eigentlich Rekursion? Ich glaube, Rekursion ist so das Lieblingskonstrukt in Programmieraufgaben und auch im wissenschaftlichen Umfeld und natürlich auch seit einiger Zeit jetzt irgendwie in der normalen Welt angekommen, nämlich durch die funktionale Programmierung, die ja früher auch eher so im wissenschaftlichen Umfeld anzutreffen war, aber jetzt seit Scala und Kotlin und JavaScript ja doch auch irgendwie Anklang findet und immer mehr Features auch in normalen prozeduralen Programmiersprachen einfließen. Und ein sehr wichtiges Konstrukt in funktionaler Programmierung ist natürlich auch die Rekursion. Sollte es Leute geben, die nicht wissen, was Rekursion ist, vielleicht noch mal grad schnell zur Erklärung. Die Rekursion ist eine Funktion, die sich selbst aufruft. Also man hat Funktionskopf, z.B. summe von einer Liste, z.B. sum list von einer verketteten Liste. Bilde mir die Summe über alle Elemente in dieser verketteten Liste. Und in der Funktion selbst gibt es dann noch einmal einen Aufruf von dieser Funktion sum list. Also die Funktion ruft sich in irgendeiner Form selbst auf. Üblicherweise hat man da auf jeden Fall eine Abbruchbedingung in dieser rekursiven Funktion, weil sonst würde die ganze Funktion ja endlos laufen in einer Endlosschleife, weil die sich immer wieder selbst aufruft. Das heißt, man hat üblicherweise irgendwo ein if Statement, wo dann ein return stattfindet, ein return zero und kein Aufruf der Funktion wieder selber stattfindet, damit man aus diesem Zykl, aus dieser Schleife überhaupt ausbrechen kann. Wenn man sich jetzt dieses Beispiel von der Summenfunktion von einer verketteten Liste genauer ansieht, dann hat man da im Prinzip zwei Zeilen in dieser Funktion, also man bekommt einen Knoten übergeben, im Normalfall der Startknoten zu Beginn und wenn es keine weitere Kinderknoten gibt, dann returnt man zero, also gibt null zurück. Oder wenn es noch weitere Kinderknoten gibt, dann macht man ein return von dem aktuellen Knotenwert von der Zahl plus sum list von dem Kind Knoten, von dem nächsten Knoten. Das heißt, man berechnet iterativ in einer Schleife alle Untersummen aus und dann am Ende wird das alles wieder zurückgegeben und in einer langen Kette von Additionen zusammengerechnet. So kann man eine Summe rekursiv bilden von einer verketteten Liste. Jetzt muss man sich überlegen, dass mit jedem Funktionsaufruf normalerweise der aktuelle State auf einen Stack gelegt wird, wo man sich gerade befindet. Und in einer rekursiven Funktion wird dann mit jedem unter Aufruf natürlich der aktuelle State auf den Stack gelegt, müssen neue Variablen und Speicher allokiert werden, vor allem wenn da natürlich komplexere Berechnungen durchgeführt werden. Und vor allem, es muss sich eben gemerkt werden, was ist der aktuelle Wert plus die Summe von allen folgenden Knoten. Das heißt, ich muss mir das irgendwie merken, wo ich gerade bin, weil die Summe der folgenden Knoten, die kommt ja erst in der Zukunft und die muss erst berechnet werden. Und genau da ist das Problem, wenn jetzt meine Liste extrem lang ist, dann laufe ich in einen Stack overflow, also mein Stack wird zu voll, zu groß. Und da steigen Programmiersprachen auch sehr schnell aus. Also BHB hatte lange ein Limit von 100 Stack Calls, was natürlich bei einer Rekursion von einer verketteten Liste sofort erreicht ist. Python hat 1000, das heißt, da rennt man sehr schnell in Limitierungen, wenn man Rekursion verwendet. Jetzt habe ich schon erwähnt, in der funktionalen Programmierung ist es aber gang und gäbe, Rekursion drin zu haben, ist viel stärker als jetzt irgendwelche Schleifen z.B. zu haben. Und da stellt sich natürlich die Frage, wie machen das die funktionalen Programmiersprachen, weil man könnte ja dann keine Liste mit über 100 Werten z.b. aufsummieren mit einer Rekursion. Und genau da kommt die Endrekursion oder Tail recursion ins Spiel. Und Endrekursion ist jetzt so definiert, dass der rekursive Aufruf in der Funktion Ÿousand der letzte Aufruf in dieser Funktion ist. Also das letzte Statement, was in irgendeiner Form ausgeführt wird, ist der eigentliche rekursive Aufruf, ohne dass man da dann irgendwie auf das Ergebnis warten muss und vielleicht was summiert. Also es wird danach kein Code mehr ausgeführt, wenn der rekursive Aufruf stattgefunden hat. Man kann natürlich die meisten Funktionen auch umschreiben von einer normalen Rekursion in eine Tail Recursion zweitausendein. Man verwendet da meistens so Akkumulatoren, das wäre jetzt bei meinem Beispiel sum List von der verketteten Liste eben die Summe bilden, würde man es dann leicht umbauen. Und zwar hat man natürlich als Parameter wieder einen Knoten für die Funktion, wo man gerade steckt in der Berechnung. Und jetzt fügen wir noch einen Akkumulator hinzu, quasi einen State, den wir mitziehen von unserer Summe, die wir gerade aktuell berechnen. Das heißt, wir haben zwei Parameter, einen Knoten, einen Akkumulator. Und in der Funktion haben wir jetzt eigentlich wieder ein ähnliches Vorgehen. Wenn es keine weiteren Knoten gibt, also keine Pointer auf einen nächsten Knoten, dann geben wir einfach den Akkumulator zurück, also einfach diese Variable ack z.B. und wenn wir noch Kinderknoten haben, dann geben wir zurück return sumlist, also machen wieder den rekursiven Aufruf. Und als Parameter übergeben wir natürlich wieder den nächsten Knoten, klarerweise, den brauchen wir. Und als zweiten Parameter nehmen wir den Akkumulator, also ack plus den aktuellen Wert von diesem Knoten. Das heißt, wir berechnen das in den Parameter und übergeben diesen. Das heißt, wir ziehen den State von der Summe, die aktuell gerade gültig ist, geben wir einfach als Parameter in die nächste Schleife, sozusagen in den nächsten Durchgang von dieser Rekursion mit. Das ermöglicht uns, dass wir eigentlich nicht mehr zurück müssen. Das heißt, wenn wir durch den rekursiven Ablauf vollständig durchgegangen sind, ganz am Ende haben wir schon in dem Akkumulator das finale Ergebnis. Das heißt, man muss nicht wieder alle Schritte zurück machen, um irgendwas zu summieren, sondern wir machen das Schritt für Schritt und können quasi den State vergessen, müssen uns nicht merken, wo wir jetzt gerade im Funktionsaufruf sind, weil wir den einfach mitschleppen, mitziehen und am Ende schon zur Verfügung haben. Und genau dann spricht man eben von einer Entrekursion. Jetzt, was hat das natürlich für einen Vorteil, wie gesagt, man hat am Ende eigentlich schon das Ergebnis. Jetzt ist natürlich so, wenn der Compiler dumm ist oder einfach das ganz normal abarbeitet, dann würde der natürlich nicht verstehen, dass es da eine Entrekursion gibt und er würde ganz normal den Stack aufbauen, weil der weiß ja nicht, dass man jetzt intelligent programmiert hat und das Ergebnis schon mitschleppt, dass man am Ende eigentlich das Ergebnis schon zur Verfügung hätte. Und darum haben ganz viele Compiler, vor allem in der funktionalen Welt, spezielle Optimierungen eingebaut, die sogenannte Tail Call Optimization, die genau diese Analyse macht. Haben wir eine Endrekursion und wenn wir eine Endrekursion haben, dann spare ich mir die Allokation des Speichers des Dates zweitausendeinundzwanzig, sondern kann bei jedem rekursiven Call den Stack wiederverwenden, also meine allokierten Variablen, den State, weil ich den einfach überschreiben kann, weil ich sicher bin, ich brauche diesen State später nicht mehr. Ich kann das alles wiederverwenden und habe im Prinzip so keinen Stack Overflow mehr. Diese Tail Call Optimization, oder TCO genannt, wird unterstützt von Scala, Haskell, Scheme, Zweitausendein, F Sharp, Lisp und sogar teilweise in JavaScript. Ab ECMAScript sechs ist es eigentlich im Standard definiert unter einer Voraussetzung, man muss dieses use strict Keyword verwenden, weil sonst gibt es ein paar Probleme mit der Umsetzung. Das andere Problem, was wir mit JavaScript noch haben, ist, dass es kaum Browser unterstützen. Die einzige browser Engine, die es gab, war Webkit, die das TCO vollständig implementiert hatte. Node, JS und Chrome, eben die v Engine, haben das nie vollständig supportet, weil sie sagen, es gibt da gewisse Performance Trade offs und Implementierungsprobleme und haben das darum leider nie vollständig implementiert. Jetzt fragen sich vielleicht, was ist denn mit der JVM und solchen Sprachen? Die JVM unterstützt es grundsätzlich nicht, aber es gibt ja auch so mehr funktionale Ansätze in Scala und Kotlin und die implementieren z.B. eigene Workarounds, die die Rekursion umbauen in Schleifen, bevor sie dann den JVM Bytecode erzeugen. Also die machen die Optimierung früher und bauen das ganze dann in Schleifen um, weil man kann ganz viele Rekursionen eigentlich immer auf eine Version in einer Schleife umbauen. Also man merkt schon, was früher eigentlich eher so als no Go gegolten hat und Rekursion hat man eher nur ganz selten eingesetzt, vor allem im prozeduralen zweitausendein Programmiersprachen. Weil es eben teilweise schwer verständlich ist, weil es Probleme mit dem Stack Overflow gegeben hat, ist es mittlerweile wesentlich besser und wird schon besser unterstützt. Also wenn ihr mal überlegt, eine Rekursion zu machen, vor allem in den funktionalen Programmiersprachen, JavaScript ist jedoch auch überall mittlerweile, dann überlegt euch mal bei der nächsten Rekursion, ob ihr nicht dem Compiler einen gefallen tut und wahrscheinlich auch eurem Stack und das ganze auf Entrekursion umbaut, weil ganz oft ist es ja wirklich einfach ein Parameter mehr oder man muss sich kurz überlegen, was man optimiert und hat dadurch dann ein Programm, was einfach nicht mehr in den Stack Overflow rennen kann und natürlich viel performanter ist, wenn der Stack immer wieder verwendet werden kann und das Date nicht jedes mal neu gespeichert werden muss. Also gibt es jetzt eigentlich fast keine Ausrede mehr, Rekursion zu verwenden. Gebt dem ganz normal eine Chance, kann euch versichern, es ist wirklich ein cooles Gefühl, wenn man mal so durch so einen riesen Baum mit einer ganz kleinen optimierten rekursiven Funktion so durchgelaufen ist und da wirklich sehr viel Codezeilen sparen kann, wenn man die Rekursion verwendet. Und damit zurück zu Andi.

Andy Grunwald (00:11:28 - 00:11:57) Teilen

Danke, Herr Dr. Wir hoffen, du konntest etwas mitnehmen. Wenn dir der Adventskalender gefällt oder du den Engineering Podcast supporten möchtest, bewerte uns doch einfach auf einer Streaming Plattform deiner Wahl. Wenn du Wolfgang und mir auch ein kleines Weihnachtsgeschenk machen würdest, kannst du uns auch einen Kaffee über die Plattform Buy me a coffee ausgeben, denn ohne Kaffee läuft bei uns leider halt auch nichts. Den Link dazu findest du in den Shownotes. Wir wünschen dir frohe Festtage und hören uns in der nächsten Episode wieder. Bis bald.

Wolfi Gassler (00:11:58 - 00:11:59) Teilen

Ÿousand.