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 Reursion 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 Algorthmen, 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.

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