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 stehen im Gegensatz zu iterativen Funktionen, die Schleifen benutzen.

Damit sie das nicht endlos tun, muss jede rekursive Funktion eine Bedingung formulieren, in der sie sich nicht weiter selbst aufruft.

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.

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

Die Fakultät Fakultät einer natürlichen Zahl n (geschrieben n!) ist das Produkt von n mit allen natürlichen Zahlen zwischen 1 und n. Beispielsweise ist

5! = 5 * 4 * 3 * 2 * 1 = 120

Diese Funktion soll beispielhaft rekursiv berechnet werden. Als Basisfall gilt, dass 1! = 1 ist.

function Factorial(_X)
    -- Basisfall: Wenn _X = 1 ist, ist das Ergebnis 1
    if _X == 1 then
        return 1
    end
 
    -- In jedem anderen Fall ist das Ergebnis das Produkt zwischen _X und der Fakultät der
    -- nächstkleineren Zahl
    return _X * Factorial(_X - 1)
end

Diese Funktion erfüllt die zwei Bedingungen, die Rekursion braucht, um funktionieren zu können:

1. Es gibt eine Abbruchbedingung, bei der kein rekursiver Aufruf stattfindet
2. 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“:

Factorial(4)                   <- _X ist hier größer als 1, also rekursiver Aufruf:
  4 * Factorial(3)             <- _X ist hier größer als 1, also rekursiver Aufruf; Factorial(3) ist noch unbekannt
    4 * 3 * Factorial(2)       <- _X ist hier größer als 1, also rekursiver Aufruf; Factorial(2) ist noch unbekannt
      4 * 3 * 2 * Factorial(1) <- _X ist gleich 1, also kann eine sichere Antwort, 1, gegeben werden
      4 * 3 * 2 * 1            <- jetzt können die zuvor unbekannten Ergebnisse oben berechnet werden
    4 * 3 * 2                  <- an der Stelle ist bekannt: Factorial(2) = 2
  4 * 6                        <- an der Stelle ist bekannt: Factorial(3) = 6
24                             <- an der Stelle ist bekannt: Factorial(4) = 24, das Ergebnis ist fertig

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.

Die Voraussetzung, eine Abbruchbedingung zu haben, um nicht im Programmablauf stecken zu bleiben, erinnert daran, dass bei 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 ersten Kapitel zu while-Schleifen in eine rekursive Variante um:

-- 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

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:

-- 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

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 Haskell beispielsweise besitzen keine Syntax für Schleifen, sodass alle Funktionen rekursiv sein müssen.

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:

return _X * Factorial(_X - 1)

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 entsprechenden Abschnitt zu Funktionsaufrufen).

-- 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

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:

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
      24

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 Minmax-Algorithmus. Der ist für Standard-Siedler zwar nicht relevant, findet jedoch z.B. in dieser Schach-Map Anwendung.

Im nächsten Kapitel diskutieren wir einige Arten von Komfortfunktionen, die die Programmierung von Missionen in Siedler vereinfachen.

Voriges Kapitel: Weiteres zu Funktionen
Nächstes Kapitel: Komfortfunktionen
Zurück nach oben