Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- scripting:tutorials:level2:recursion [2023/11/23 16:27] – angelegt fritz_98
+++ scripting:tutorials:level2:recursion [2023/11/24 10:06] (aktuell) – [Endrekursion] fritz_98
@@ Zeile 1: / Zeile 1: @@
 ======Rekursionen======
-Rekursive Funktionen sind Funktionen, die sich während ihrer Ausführung selbst aufrufen. Dabei kann sich die Funktion sogar mehrmals selbst oder zwei Funktionen sich gegenseitig aufrufen.
+Rekursive Funktionen sind Funktionen, die sich während ihrer Ausführung selbst aufrufen. Dabei kann sich die Funktion sogar mehrmals selbst oder zwei Funktionen sich gegenseitig aufrufen. Rekursive Funktionen stehen im Gegensatz zu iterativen Funktionen, die [[ scripting:tutorials:level1:loops|Schleifen]] benutzen.
 Damit sie das nicht endlos tun, muss jede rekursive Funktion eine Bedingung formulieren, in der sie sich **nicht** weiter selbst aufruft.
@@ Zeile 7: / Zeile 7: @@
 Jede rekursive Funktion besitzt demnach einen Basisfall bzw. eine Abbruchbedingung, bei der keine weiteren rekursiven Aufrufe mehr geschehen. Trifft diese Abbruchbedingung nicht zu, geschieht der rekursive Aufruf. Der rekursive Aufruf darf dabei **nicht** mit den gleichen Argumenten geschehen, die die Funktion selbst erhält, da sonst die Abbruchbedingung nie erreicht werden kann, wodurch die Berechnung nie beendet wird. Die Idee ist also, dass das Ergebnis Schritt für Schritt berechnet wird und jeder rekursive Aufruf einen "kleineren" Parameter weitergibt, als er selbst bekommen hat.
-Verdeutlicht an einem Beispiel:
+----
+**Hinweis**: Unsere Beispiele in diesem und den folgenden Kapiteln können besser nachvollzogen werden, wenn man die Programmzeilen nebenbei ausprobieren kann. Dazu kann man diese Webseite hier verwenden:
+[[ https://www.lua.org/demo.html ]]
+----
 ====Beispiel: Berechnung der Fakultät====
@@ Zeile 31: / Zeile 37: @@
   - Es gibt eine Abbruchbedingung, bei der kein rekursiver Aufruf stattfindet
-  - Der rekursive Aufruf gibt als Argument eine kleinere Zahl (''_X - 1'') weiter, als der Funktionsaufruf selbst bekommen hat. So wird sichergestellt, dass die Abbruchbedingung immer erreicht wird (vorausgesetzt, die eingegebene Zahl war positiv)
+  - Der rekursive Aufruf gibt als Argument eine kleinere Zahl (''_X - 1'') weiter, als der Funktionsaufruf selbst bekommen hat. So wird sichergestellt, dass die Abbruchbedingung immer erreicht wird (vorausgesetzt, die eingegebene Zahl war ≥ 1)
 Zur Veranschaulichung können wir den Funktionsaufruf ''Factorial(4)'' "aufrollen":
@@ Zeile 45: / Zeile 51: @@
                              <- an der Stelle ist bekannt: Factorial(4) = 24, das Ergebnis ist fertig
 </code>
+**Hinweis**: Die Fakultät einer Zahl //n// wird sehr schnell sehr groß. Da die Zahlen, die Lua darstellen kann, eine Maximalgröße haben, werden die Ergebnisse in Siedler und in der Lua Demo für ausreichend hohe //n// falsch sein.
 \\
 ====Zusammenhang mit Schleifen====
-(+ Beispiel Fibonacci, Fakultät)
+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 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>
+-- Rekursive Variante des Euklidischen Algorithmus
+function GreatestCommonDivisor(_A, _B)
+    -- Diese Abbruchbedingung war bereits Teil der ursprünglichen Formulierung
+    if _A == 0 then
+        return _B
+    end
+    -- Diese Abbruchbedingung ist die gleiche wie die der while-Schleife in der ursprünglichen
+    -- Formulierung. Auch in der Schleifen-Version des Algorithmus wird _A zurückgegeben, sobald
+    -- _B == 0 ist. Damit in diesem Fall keine weiteren rekursiven Aufrufe mehr passieren,
+    -- steht diese Bedingung hier oben
+    if _B == 0 then
+        return _A
+    end
+    -- Diese Bedingung ist ebenfalls die gleiche wie in der ursprünglichen Formulierung
+    -- Die Fallunterscheidung entscheidet, welcher der beiden Parameter um den jeweils anderen
+    -- verringert wird. Dadurch wird sichergestellt, dass wir in keiner Endlosrekursion landen:
+    -- Da sowohl _A als auch _B an der Stelle größer 0 sein müssen (sonst wäre die Funktion oben
+    -- bereits mit return ausgestiegen), wird einer der Parameter echt kleiner, nähert sich also
+    -- zwangsweise der 0, was die Abbruchbedingung ist
+    -- Der Rekursive Aufruf geschieht pro Funktionsaufruf höchstens 1 mal, da nur einer der beiden
+    -- Fälle eintreten kann
+    if _A > _B then
+        return GreatestCommonDivisor(_A - _B, _B)
+    else
+        return GreatestCommonDivisor(_A, _B - _A)
+    end
+end
+</code>
+Umgekehrt muss es auch möglich sein, rekursive Funktionen durch Schleifen auszudrücken. Die Berechnung der Fakultät in einer Schleife sähe so aus:
+<code lua>
+-- Iterative Version der Berechung der Fakultät
+function Factorial(_X)
+    local Result = 1
+    while _X > 1 do
+       Result = Result * _X
+       _X = _X - 1
+    end
+    return Result
+end
+</code>
+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.
+\\
+====Endrekursion====
+Die Art und Weise, wie wir oben die Fakultät rekursiv definiert haben, kann für größere Funktionen zu Performanceproblemen führen. Das hat folgenden Grund: Bei jedem rekursiven Aufruf muss sich Lua merken, wie "tief" die Rekursion bereits fortgeschritten ist, um beim Erreichen der Abbruchbedingung wieder zurück zum Ausgangspunkt des ersten Funktionsaufrufs zu finden. Diesen Ausgangspunkt muss Lua finden, weil nach dem rekursiven Aufruf noch eine Multiplikation stattfinden soll. Zur Erinnerung: Der rekursive Aufruf sieht so aus:
+<code lua>
+return _X * Factorial(_X - 1)
+</code>
+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>
+----
-====Endrekrusion====
+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.
-====Relevanz in Lua====
+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:comfort_functions | Nächstes Kapitel: Komfortfunktionen  ]] \\
+[[ scripting:tutorials:level2:recursion | Zurück nach oben ]]