Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- scripting:tutorials:level2:recursion [2023/11/24 09:05] – fritz_98
+++ scripting:tutorials:level2:recursion [2023/11/24 10:06] (aktuell) – [Endrekursion] fritz_98
@@ Zeile 60: / Zeile 60: @@
 Die Voraussetzung, eine Abbruchbedingung zu haben, um nicht im Programmablauf stecken zu bleiben, erinnert daran, dass bei [[ scripting:tutorials:level1:loops |Schleifen]] ebenfalls darauf geachtet werden muss, Endlosschleifen zu vermeiden. Tatsächlich können mit Schleifen und Rekursionen die gleichen Algorithmen ausgedrückt werden, solange sich eine Funktion pro Aufruf **höchstens 1 mal** selbst erneut aufruft. Welchen der beiden Ansätze man in so einem Fall wählt, hängt in erster Linie davon ab, was einem leichter fällt zu formulieren.
-Um diese Behauptung zu untermauern und ein weiteres rekursives Beispiel zu geben, wollen wir eine bereits bekannte Funktion, die Schleifen beinhalten, als Reursion ausdrücken. Wir wandeln den Algorithmus zur Bestimmung des größten gemeinsamen Teilers aus dem [[ scripting:tutorials:level1:loops#while-schleife|ersten Kapitel zu while-Schleifen]] in eine rekursive Variante um:
+Um diese Behauptung zu untermauern und ein weiteres rekursives Beispiel zu geben, wollen wir eine bereits bekannte Funktion, die Schleifen beinhalten, als Rekursion ausdrücken. Wir wandeln den Algorithmus zur Bestimmung des größten gemeinsamen Teilers aus dem [[ scripting:tutorials:level1:loops#while-schleife|ersten Kapitel zu while-Schleifen]] in eine rekursive Variante um:
 <code lua>
@@ Zeile 106: / Zeile 106: @@
 end
 </code>
-Es gibt einige Algorthmen, die deutlich besser rekursiv als iterativ auszudrücken sind und umgekehrt. Prinzipiell hat man aber immer die Wahl. Einige Programmiersprachen wie [[ https://de.wikipedia.org/wiki/Haskell_(Programmiersprache)|Haskell]] beispielsweise besitzen keine Syntax für Schleifen, sodass alle Funktionen rekursiv sein müssen.
+Es gibt einige Algorithmen, die deutlich besser rekursiv als iterativ auszudrücken sind und umgekehrt. Prinzipiell hat man aber immer die Wahl. Einige Programmiersprachen wie [[ https://de.wikipedia.org/wiki/Haskell_(Programmiersprache)|Haskell]] beispielsweise besitzen keine Syntax für Schleifen, sodass alle Funktionen rekursiv sein müssen.
 \\
@@ Zeile 118: / Zeile 118: @@
 Das Programm muss also zuerst ''Factorial(_X - 1)'' berechnen, zurück zum Ausgangspunkt kommen und dann das Ergebnis mit ''_X'' multiplizieren.
+Lua profitiert allerdings von endrekursiven Formulierungen: Wenn im **return** nur ein Funktionsaufruf steht, weiß das Programm, dass es nicht mehr an den Ausgangspunkt zurückkehren muss und spart sich die Buchführung. Damit das Funktioniert, muss das Zwischenergebnis, das zuvor durch die "Kette" an Multiplikationen nicht gebraucht wurde, irgendwo festgehalten werden, so wie es bei der iterativen Formulierung oben mit der Variable ''Result'' geschieht.
+Zu dem Zweck soll die Funktion ''Factorial'' einen zweiten Parameter bekommen, der das Zwischenergebnis enthält. Für den Aufruf der Funktion soll er **nil** sein dürfen und wird in dem Fall mit einem Standardwert befüllt (siehe auch im [[ scripting:tutorials:level2:functions#zu_viele_und_zu_wenige_parameter|entsprechenden Abschnitt zu Funktionsaufrufen]]).
+<code lua>
+-- Der zweite Parameter _Acc steht für "Accumulator", also der "Sammler" für Zwischenergebnisse
+function Factorial(_X, _Acc)
+    -- Schreibe 1 ins Zwischenergebnis, falls es noch keines gibt
+    -- Dieser Fall ist nur für den ersten Aufruf der Funktion relevant
+    if not _Acc then
+        _Acc = 1
+    end
+    -- Das Zwischenergebnis wird bei jeder Rekursion "mitgenommen". Deshalb reicht es,
+    -- dieses Zwischenergebnis im Basisfall auszugeben
+    if _X == 1 then
+        return _Acc
+    end
+    -- Das neue Zwischenergebnis ist das Produkt aus _X und dem bisherigen Zwischenergebnis
+    return Factorial(_X - 1, _X * _Acc)
+end
+</code>
+So aufgeschrieben muss die Funktion nach dem rekursiven Aufruf nichts mehr mit dem Ergebnis machen. Das Zwischenergebnis wird dem rekursiven Aufruf weitergereicht, die lange Kette an Multiplikationen, die rückwärts wieder abgearbeitet werden muss, existiert nicht mehr. Das wird deutlich, wenn wir die Rechnung wie oben "aufrollen" und die beiden Varianten miteinander vergleichen:
+<code>
+Factorial(4)           <- _X ist hier größer als 1, also rekursiver Aufruf
+  Factorial(3, 4)      <- _X ist hier größer als 1, also rekursiver Aufruf
+    Factorial(2, 12)   <- _X ist hier größer als 1, also rekursiver Aufruf
+      Factorial(1, 24) <- _X ist gleich 1, das Ergebnis wurde über die vorigen Aufrufe berechnet
+</code>
 ----
-Dieses Kapitel zu Rekursionen dient hauptsächlich zum Verständnis des Konzepts. Vielen fällt die Fomurlierung in Schleifen leichter als Rekursionen. Wahrscheinlich findest du in Skripten anderer Mapper aber immer wieder rekursive Funktionen, auch solche, die sich nicht iterativ ausdrücken lassen (wegen beispielsweise mehrerer rekursiver Aufrufe). Ein anderes Beispiel ist der [[ https://de.wikipedia.org/wiki/Minimax-Algorithmus|Minmax-Algorithmus]]. Der ist für Standard-Siedler zwar nicht relevant, findet jedoch z.B. in dieser [[ https://www.siedler-maps.de/maps/Schach-1252.htm|Schach-Map]] Anwendung.
+Dieses Kapitel zu Rekursionen dient hauptsächlich zum Verständnis des Konzepts. Vielen fällt die Formulierung in Schleifen leichter als Rekursionen. Wahrscheinlich findest du in Skripten anderer Mapper aber immer wieder rekursive Funktionen, auch solche, die sich nicht iterativ ausdrücken lassen (wegen beispielsweise mehrerer rekursiver Aufrufe). Ein anderes Beispiel ist der [[ https://de.wikipedia.org/wiki/Minimax-Algorithmus|Minmax-Algorithmus]]. Der ist für Standard-Siedler zwar nicht relevant, findet jedoch z.B. in dieser [[ https://www.siedler-maps.de/maps/Schach-1252.htm|Schach-Map]] Anwendung.
 Im nächsten Kapitel diskutieren wir einige Arten von Komfortfunktionen, die die Programmierung von Missionen in Siedler vereinfachen.
 [[ scripting:tutorials:level2:functions| Voriges Kapitel: Weiteres zu Funktionen  ]] \\
-[[ scripting:tutorials:level2:recursion | Nächstes Kapitel: Komfortfunktionen  ]] \\
+[[ scripting:tutorials:level2:comfort_functions | Nächstes Kapitel: Komfortfunktionen  ]] \\
 [[ scripting:tutorials:level2:recursion | Zurück nach oben ]]