Rekursion in Lua
Implementieren Sie rekursive Algorithmen und verstehen Sie Luas Optimierung von Tail Calls
Rekursion in Lua ist eine kostenlose Lua Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Lua Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Lua Academy-Kurs umfasst insgesamt 4 Lektionen.
Was ist Rekursion?
Rekursion bedeutet, dass eine Funktion sich selbst aufruft, um eine kleinere Instanz desselben Problems zu lösen. Jede rekursive Funktion benötigt einen Basisfall (an dem sie endet) und einen rekursiven Fall (in dem sie das Problem verkleinert). Ohne Basisfall führt Rekursion zu einem Stacküberlauf.
local function countdown(n)
if n <= 0 then
print("Blast off!")
return
end
print(n)
countdown(n - 1)
end
countdown(5)
-- 5, 4, 3, 2, 1, Blast off!Fakultät
Die Fakultät ist das klassische Rekursionsbeispiel: n! = n × (n-1)! mit dem Basisfall 0! = 1. Jeder Aufruf verringert n um 1, bis der Basisfall erreicht ist. Die Ergebnisse werden auf dem Aufruf-Stack wieder „abgewickelt“ und dabei miteinander multipliziert.
local function factorial(n)
if n <= 1 then return 1 end
return n * factorial(n - 1)
end
print(factorial(1)) -- 1
print(factorial(5)) -- 120
print(factorial(10)) -- 3628800Fibonacci
Die Fibonacci-Folge ist ein weiteres klassisches Beispiel: fib(n) = fib(n-1) + fib(n-2). Naive Rekursion hat exponentielle Laufzeit, da dieselben Werte wiederholt berechnet werden. Wir sehen uns als Lösung die Memoisierung an, beginnen aber zunächst mit der Grundform.
local function fib(n)
if n <= 1 then return n end
return fib(n - 1) + fib(n - 2)
end
for i = 0, 10 do
io.write(fib(i) .. " ")
end
print()
-- 0 1 1 2 3 5 8 13 21 34 55Memoisierte Rekursion
Bei der Memoisierung werden zuvor berechnete Ergebnisse in einer Tabelle zwischengespeichert. Prüfen Sie bei jedem Aufruf zuerst den Cache. Wenn der Wert vorhanden ist, geben Sie ihn sofort zurück. Andernfalls berechnen und speichern Sie ihn. Dadurch wird die exponentielle Laufzeit der Fibonacci-Berechnung linear.
local memo = {}
local function fib(n)
if memo[n] then return memo[n] end
if n <= 1 then return n end
local result = fib(n-1) + fib(n-2)
memo[n] = result
return result
end
print(fib(40)) -- 102334155 (fast!)Optimierung von Tail Calls
Lua führt eine Tail-Call-Optimierung (TCO) durch: Wenn die letzte Aktion einer Funktion der Aufruf einer anderen Funktion ist, verwendet Lua den aktuellen Stack-Frame wieder. Dadurch benötigen tail-rekursive Funktionen konstanten Stack-Speicher von O(1). Nicht jede Rekursion ist tail-rekursiv — der Aufruf muss das Letzte in der Funktion sein.
-- Tail-recursive factorial using accumulator
local function factTail(n, acc)
acc = acc or 1
if n <= 1 then return acc end
return factTail(n - 1, n * acc) -- tail call
end
print(factTail(10)) -- 3628800
-- Can handle very large n without stack overflowBaumdurchlauf
Rekursion eignet sich besonders gut, um Baumdurchläufe auszudrücken. Ein Baum ist eine Tabelle mit den Feldern value, left und right. Preorder-, Inorder- und Postorder-Durchläufe unterscheiden sich nur darin, wann der Wert im Verhältnis zu den rekursiven Aufrufen verarbeitet wird.
local function inorder(node)
if node == nil then return end
inorder(node.left)
io.write(node.value .. " ")
inorder(node.right)
end
local tree = {
value=4,
left={value=2, left={value=1}, right={value=3}},
right={value=6, left={value=5}, right={value=7}}
}
inorder(tree) -- 1 2 3 4 5 6 7Gegenseitige Rekursion
Zwei Funktionen können sich gegenseitig aufrufen (gegenseitige Rekursion). In Lua benötigen Sie dafür Vorwärtsdeklarationen: Deklarieren Sie zuerst lokale Variablen und weisen Sie ihnen anschließend die Funktionen zu. So kann jede Funktion auf die Variable der anderen verweisen, die sich bereits im Gültigkeitsbereich befindet.
local isEven, isOdd
isEven = function(n)
if n == 0 then return true end
return isOdd(n - 1)
end
isOdd = function(n)
if n == 0 then return false end
return isEven(n - 1)
end
print(isEven(10)) -- true
print(isOdd(7)) -- trueRekursives Deep Copy
Rekursion eignet sich ideal für Operationen auf verschachtelten Strukturen. Eine Tabelle tief zu kopieren bedeutet, ihren Inhalt zu kopieren und alle verschachtelten Tabellen rekursiv ebenfalls zu kopieren (sodass Änderungen an der Kopie das Original nicht beeinflussen).
local function deepCopy(orig)
local copy
if type(orig) == "table" then
copy = {}
for k, v in pairs(orig) do
copy[deepCopy(k)] = deepCopy(v)
end
setmetatable(copy, getmetatable(orig))
else
copy = orig
end
return copy
end
local a = {1, {2, 3}}
local b = deepCopy(a)
b[2][1] = 99
print(a[2][1]) -- 2 (unchanged)Flood-Fill-Algorithmus
Flood Fill (verwendet in Malprogrammen und Spielkarten) lässt sich auf natürliche Weise rekursiv umsetzen. Beginnen Sie bei einer Zelle, markieren Sie sie und füllen Sie anschließend rekursiv jeden noch nicht besuchten Nachbarn. Die Rekursion endet an Grenzen oder bei bereits besuchten Zellen.
local grid = {
{0,0,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
}
local function fill(g, r, c)
if r<1 or r>#g or c<1 or c>#g[r] then return end
if g[r][c] ~= 0 then return end
g[r][c] = 2 -- mark visited
fill(g,r-1,c); fill(g,r+1,c)
fill(g,r,c-1); fill(g,r,c+1)
end
fill(grid, 1, 1)
print(grid[1][1], grid[2][1]) -- 2 2Stacktiefe beachten
Der Standard-Aufruf-Stack von Lua ist begrenzt (typischerweise auf etwa 200 Ebenen bei nicht-tail-rekursiven Aufrufen). Tiefe nicht-tail-rekursive Aufrufe verursachen einen Fehler wegen eines „Stacküberlaufs“. Lösungen sind die Umwandlung in Tail-Rekursion, die Verwendung eines expliziten Stacks (Tabelle) oder Coroutines für große iterative Aufgaben.
-- Simulate deep recursion danger
local function depth(n)
if n == 0 then return "done" end
return depth(n - 1) -- tail call, safe
end
print(depth(100000)) -- done (tail call, no overflow)
-- Non-tail: limited depth
local function countDown(n)
if n == 0 then return 0 end
return 1 + countDown(n - 1) -- NOT a tail call
end
-- countDown(10000) would stack overflowKurze Überprüfung
Welcher der folgenden Aufrufe ist in Lua ein korrekter Tail Call?
Rückblick: Rekursion
Zusammenfassung:
- Jede rekursive Funktion benötigt einen Basisfall und einen rekursiven Fall
- Tail Calls (die letzte Aktion ist ein Aufruf) werden von Lua optimiert — Stackbedarf O(1)
- Memoisierung wandelt exponentielle Rekursion in lineare Laufzeit um
- Gegenseitige Rekursion erfordert Vorwärtsdeklarationen
- Tiefe Rekursion bei Bäumen und Graphen ist natürlich; achten Sie bei nicht-tail-rekursiven Aufrufen auf die Stacktiefe
Häufig gestellte Fragen
Ist die Lektion „Rekursion in Lua“ kostenlos?
Ja — der vollständige Text von „Rekursion in Lua“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Lua Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Lua Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Rekursion in Lua“?
Implementieren Sie rekursive Algorithmen und verstehen Sie Luas Optimierung von Tail Calls Du übst Lua Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Lua Academy zu starten?
Keine Vorkenntnisse erforderlich. Lua Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Rekursion in Lua“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Lua Academy-Lektion Code schreiben und ausführen?
Ja. Jede Lua Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.