Recursie in Lua
Implementeer recursieve algoritmen en begrijp Lua's optimalisatie van staartaanroepen
Recursie in Lua is een gratis Lua Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Lua Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Lua Academy bevat in totaal 4 lessen.
Wat is recursie?
Recursie betekent dat een functie zichzelf aanroept om een kleinere versie van hetzelfde probleem op te lossen. Elke recursieve functie heeft een basisgeval nodig (waarbij de functie stopt) en een recursief geval (waarbij het probleem kleiner wordt gemaakt). Zonder basisgeval veroorzaakt recursie een stackoverflow.
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!Faculteit
De faculteit is het klassieke voorbeeld van recursie: n! = n × (n-1)! met als basisgeval 0! = 1. Elke aanroep vermindert n met 1 totdat het basisgeval is bereikt. De resultaten worden weer teruggevoerd door de aanroepstack en daarbij met elkaar vermenigvuldigd.
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
De rij van Fibonacci is een ander klassiek voorbeeld: fib(n) = fib(n-1) + fib(n-2). Naïeve recursie heeft exponentiële complexiteit — dezelfde waarden worden steeds opnieuw berekend. We bekijken memoization als oplossing, maar eerst de basisvorm.
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 55Recursie met memoization
Memoization slaat eerder berekende resultaten op in een tabel. Controleer bij elke aanroep eerst de cache. Staat de waarde erin, retourneer die dan onmiddellijk. Bereken en sla de waarde anders op. Hierdoor verandert Fibonacci met exponentiële tijdscomplexiteit in lineaire tijd.
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!)Optimalisatie van staartaanroepen
Lua voert optimalisatie van staartaanroepen (TCO) uit: wanneer de laatste actie van een functie een aanroep van een andere functie is, hergebruikt Lua het huidige stackframe. Daardoor gebruiken staartrecursieve functies O(1) stackruimte. Niet alle recursie is staartrecursief — de aanroep moet het laatste zijn wat de functie doet.
-- 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 overflowBomen doorlopen
Recursie is een natuurlijke manier om een boom te doorlopen. Een boom is een tabel met de velden value, left en right. Bij preorder-, inorder- en postorderdoorlopen verschilt alleen het moment waarop de waarde wordt verwerkt ten opzichte van de recursieve aanroepen.
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 7Wederzijdse recursie
Twee functies kunnen elkaar aanroepen (wederzijdse recursie). In Lua heb je voorafgaande declaraties nodig: declareer eerst lokale variabelen en wijs daarna de functies toe. Zo kan elke functie verwijzen naar de variabele van de andere functie, die al binnen de scope valt.
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)) -- trueRecursief diep kopiëren
Recursie is ideaal voor bewerkingen op geneste structuren. Een tabel diep kopiëren betekent dat je de inhoud kopieert en geneste tabellen recursief kopieert, zodat wijzigingen in de kopie geen invloed hebben op het origineel.
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)Floodfill-algoritme
Floodfill (gebruikt in tekenprogramma's en spelkaarten) leent zich van nature voor recursie. Begin bij een cel, markeer die en vul daarna recursief elke nog niet bezochte buurcel. De recursie stopt bij randen of cellen die al bezocht zijn.
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 2Bewust omgaan met stackdiepte
De standaardaanroepstack van Lua is beperkt (meestal ongeveer 200 niveaus voor niet-staartaanroepen). Diepe niet-staartrecursie veroorzaakt een fout door een "stackoverflow". Oplossingen zijn: de recursie omzetten naar staartrecursie, een expliciete stack (tabel) gebruiken of coroutines inzetten voor grote iteratieve taken.
-- 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 overflowKorte controle
Welke van de volgende aanroepen is een correcte staartaanroep in Lua?
Terugblik: recursie
Samenvatting:
- Elke recursieve functie heeft een basisgeval en een recursief geval nodig
- Staartaanroepen (waarbij de laatste actie een aanroep is) worden door Lua geoptimaliseerd — O(1) stackruimte
- Memoization zet exponentiële recursie om in lineaire tijd
- Wederzijdse recursie vereist voorafgaande declaraties
- Diepe recursie in bomen of grafen is natuurlijk; let bij niet-staartaanroepen op de stackdiepte
Leer Lua met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 40
- Lessen
- 159
Veelgestelde vragen
Is de les “Recursie in Lua” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad Lua Academy, waaronder “Recursie in Lua”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus Lua Academy bevat in totaal 4 lessen.
Wat leer ik in “Recursie in Lua”?
Implementeer recursieve algoritmen en begrijp Lua's optimalisatie van staartaanroepen Je oefent met Lua Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Lua Academy te beginnen?
Ervaring vooraf is niet nodig. Lua Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Recursie in Lua”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Lua Academy?
Ja. Elke les over Lua Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.