Rekursion i Lua
Implementér rekursive algoritmer, og forstå Lua's optimering af tail calls.
Rekursion i Lua er en gratis Lua Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i Lua Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Lua Academy-kurset indeholder 4 lektioner i alt.
Hvad er rekursion?
Rekursion opstår, når en funktion kalder sig selv for at løse en mindre udgave af det samme problem. Enhver rekursiv funktion har brug for et basistilfælde (hvor den stopper) og et rekursivt tilfælde (hvor den reducerer problemet). Uden et basistilfælde medfører rekursion et stakoverløb.
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 er det klassiske eksempel på rekursion: n! = n × (n-1)! med basistilfældet 0! = 1. Hvert kald reducerer n med 1, indtil basistilfældet nås. Resultaterne "vikles ud" op gennem kaldstakken, mens de ganges sammen.
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-følgen er et andet klassisk eksempel: fib(n) = fib(n-1) + fib(n-2). Naiv rekursion har eksponentiel tidskompleksitet — den genberegner de samme værdier igen og igen. Vi ser på memoization som en løsning, men først den grundlæggende form.
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 55Memoiseret rekursion
Memoization gemmer tidligere beregnede resultater i en tabel. Kontrollér cachen først ved hvert kald. Hvis værdien findes, returneres den med det samme. Ellers beregnes og gemmes den. Det gør Fibonacci fra eksponentiel til lineær tidskompleksitet.
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 af halekald
Lua udfører optimering af halekald (TCO): Når den sidste handling i en funktion er et kald til en anden funktion, genbruger Lua den aktuelle stack frame. Det får halerekursive funktioner til at bruge O(1) stackplads. Ikke al rekursion er halerekursiv — kaldet skal være det sidste, der sker 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 overflowGennemløb af træer
Rekursion udtrykker naturligt gennemløb af træer. Et træ er en tabel med felterne value, left og right. Gennemløb i preorder, inorder og postorder adskiller sig kun ved, hvornår værdien behandles i forhold til de rekursive kald.
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 7Gensidig rekursion
To funktioner kan kalde hinanden (gensidig rekursion). I Lua skal du bruge fremadrettede deklarationer: Deklarér først lokale variabler, og tildel derefter funktionerne. På den måde kan hver funktion referere til den andens variabel, som allerede er i scope.
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 dyb kopiering
Rekursion er velegnet til operationer på indlejrede strukturer. Dyb kopiering af en tabel betyder, at dens indhold kopieres, og at eventuelle indlejrede tabeller også kopieres rekursivt (så ændringer i kopien ikke påvirker originalen).
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 (brugt i maleprogrammer og spilkort) egner sig naturligt til rekursion. Start ved en celle, markér den, og udfyld derefter hvert ubesøgt nabofelt rekursivt. Rekursionen stopper, når den rammer en grænse eller en allerede besøgt celle.
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 2Overblik over stakdybde
Lua's standardkaldestak er begrænset (typisk omkring 200 niveauer for kald, der ikke er halekald). Dyb rekursion uden halekald medfører en fejl med "stack overflow". Løsninger er at omskrive til halerekursion, bruge en eksplicit stak (tabel) eller bruge coroutines til store iterative opgaver.
-- 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 overflowHurtigt tjek
Hvilket af følgende er et korrekt halekald i Lua?
Opsamling: Rekursion
Opsummering:
- Enhver rekursiv funktion har brug for et basistilfælde og et rekursivt tilfælde
- Halekald (hvor den sidste handling er et kald) optimeres af Lua — O(1) stack
- Memoization omdanner eksponentiel rekursion til lineær rekursion
- Gensidig rekursion kræver fremadrettede deklarationer
- Dyb rekursion i træer og grafer er naturlig; hold øje med stakdybden ved kald, der ikke er halekald
Lær Lua med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 40
- Lektioner
- 159
Ofte stillede spørgsmål
Er lektionen “Rekursion i Lua” gratis?
Ja — alle 3 lektioner i læringssporet Lua Academy, inklusive “Rekursion i Lua”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Lua Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Rekursion i Lua”?
Implementér rekursive algoritmer, og forstå Lua's optimering af tail calls. Du øver dig i Lua Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Lua Academy?
Der kræves ingen tidligere erfaring. Lua Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Rekursion i Lua”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Lua Academy-lektion?
Ja. Alle Lua Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.