Rekursion i Lua
Implementera rekursiva algoritmer och förstå Lua:s optimering av svansanrop.
Rekursion i Lua är en gratis lektion i Lua Academy på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för Lua Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Lua Academy innehåller totalt 4 lektioner.
Vad är rekursion?
Rekursion innebär att en funktion anropar sig själv för att lösa en mindre instans av samma problem. Varje rekursiv funktion behöver ett basfall, där den avslutas, och ett rekursivt fall, där problemet reduceras. Utan ett basfall orsakar rekursion ett stack overflow.
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!Fakultet
Fakultet är det klassiska rekursionsexemplet: n! = n × (n-1)! med basfallet 0! = 1. Varje anrop minskar n med 1 tills basfallet nås. Resultaten "vecklas ut" tillbaka upp genom anropsstacken och multipliceras på vägen.
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
Fibonacci-sekvensen är ett annat klassiskt exempel: fib(n) = fib(n-1) + fib(n-2). Naiv rekursion har exponentiell tidskomplexitet – samma värden beräknas om och om igen. Vi ska se hur detta löses med memoisering, men först den grundläggande formen.
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 55Rekursion med memoisering
Memoisering cachar tidigare beräknade resultat i en tabell. Kontrollera cachen först vid varje anrop. Om värdet finns där returnerar du det direkt. Annars beräknar och lagrar du det. Då omvandlas Fibonacci med exponentiell tidskomplexitet till linjär tidskomplexitet.
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!)Optimering av svansanrop
Lua utför optimering av svansanrop (TCO): när den sista åtgärden i en funktion är ett anrop till en annan funktion återanvänder Lua den aktuella stackramen. Därför använder svansrekursiva funktioner O(1) stackutrymme. All rekursion är inte svansrekursiv – anropet måste vara det sista som händer i funktionen.
-- 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 overflowTraversering av träd
Rekursion uttrycker naturligt traversering av träd. Ett träd är en tabell med fälten value, left och right. Preorder-, inorder- och postordertraversering skiljer sig endast åt i när värdet bearbetas i förhållande till de rekursiva anropen.
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 7Ömsesidig rekursion
Två funktioner kan anropa varandra, vilket kallas ömsesidig rekursion. I Lua behöver du framåtdeklarationer: deklarera lokala variabler först och tilldela sedan funktionerna. På så sätt kan varje funktion referera till den andras variabel, som redan finns i scopet.
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)) -- trueRekursiv djupkopiering
Rekursion passar utmärkt för operationer på nästlade strukturer. Att djupkopiera en tabell innebär att kopiera dess innehåll och rekursivt kopiera eventuella nästlade tabeller, så att ändringar i kopian inte påverkar originalet.
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-algoritmen
Flood fill, som används i målarprogram och spelkartor, lämpar sig naturligt för rekursion. Börja i en cell, markera den och fyll sedan rekursivt varje obesökt granne. Rekursionen avslutas när den når en gräns eller en cell som redan har besökts.
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 2Medvetenhet om stackdjup
Luas standardanropsstack är begränsad, vanligtvis till cirka 200 nivåer för anrop som inte är svansanrop. Djup icke-svansrekursion orsakar felet "stack overflow". Lösningar är att omvandla till svansrekursion, använda en explicit stack (tabell) eller använda coroutines för stora iterativa uppgifter.
-- 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 overflowSnabbkontroll
Vilket av följande är ett korrekt svansanrop i Lua?
Repetition: Rekursion
Sammanfattning:
- Varje rekursiv funktion behöver ett basfall och ett rekursivt fall
- Svansanrop, där den sista åtgärden är ett anrop, optimeras av Lua och använder O(1) stackutrymme
- Memoisering omvandlar exponentiell rekursion till linjär
- Ömsesidig rekursion kräver framåtd deklarationer
- Djup rekursion i träd och grafer är naturlig; var uppmärksam på stackdjupet vid anrop som inte är svansanrop
Lär dig Lua med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 40
- Lektioner
- 159
Vanliga frågor
Är lektionen ”Rekursion i Lua” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen Lua Academy, inklusive ”Rekursion i Lua”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i Lua Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Rekursion i Lua”?
Implementera rekursiva algoritmer och förstå Lua:s optimering av svansanrop. Ni övar på Lua Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Lua Academy?
Du behöver inga förkunskaper. Utbildningen i Lua Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Rekursion i Lua”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Lua Academy-lektionen?
Ja. Varje Lua Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.