Rekursjon i Lua
Implementer rekursive algoritmer og forstå Lua sin optimalisering av haleanrop.
Rekursjon i Lua er en gratis leksjon i Lua Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Lua Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Lua Academy inneholder totalt 4 leksjoner.
Hva er rekursjon?
Rekursjon betyr at en funksjon kaller seg selv for å løse en mindre instans av det samme problemet. Alle rekursive funksjoner trenger et basistilfelle, der den stopper, og et rekursivt tilfelle, der problemet reduseres. Uten et basistilfelle fører rekursjon til 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 er det klassiske eksempelet på rekursjon: n! = n × (n-1)! med basistilfellet 0! = 1. Hvert kall reduserer n med 1 til basistilfellet nås. Resultatene «vikles» tilbake oppover kallstakken, og multipliseres underveis.
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 annet klassisk eksempel: fib(n) = fib(n-1) + fib(n-2). Naiv rekursjon har eksponentiell kjøretid fordi de samme verdiene beregnes på nytt mange ganger. Vi skal se på memoization som en løsning, men først ser vi på grunnformen.
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 55Rekursjon med memoization
Memoization lagrer tidligere beregnede resultater i en tabell. Kontroller hurtigbufferet først ved hvert kall. Hvis verdien finnes der, returnerer De den umiddelbart. Ellers beregner og lagrer De den. Dette gjør Fibonacci med eksponentiell kjøretid lineær.
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!)Optimalisering av tail calls
Lua utfører optimalisering av tail calls (TCO): Når den siste handlingen i en funksjon er et kall til en annen funksjon, gjenbruker Lua den aktuelle stack-rammen. Dermed bruker tail-rekursive funksjoner O(1) plass på stacken. Ikke all rekursjon er tail-rekursiv – kallet må være det siste som skjer i funksjonen.
-- 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ær
Rekursjon egner seg naturlig til traversering av trær. Et tre er en tabell med feltene value, left og right. Traversering i preorder, inorder og postorder skiller seg bare i når verdien behandles i forhold til de rekursive kallene.
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 7Gjensidig rekursjon
To funksjoner kan kalle hverandre, noe som kalles gjensidig rekursjon. I Lua trenger De forhåndsdeklarasjoner: Deklarer lokale variabler først, og tilordne deretter funksjonene. Da kan hver funksjon referere til variabelen for den andre funksjonen, som allerede er innenfor 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 dyp kopiering
Rekursjon egner seg godt til operasjoner på nestede strukturer. Dyp kopiering av en tabell betyr at innholdet kopieres, og at eventuelle nestede tabeller også kopieres rekursivt, slik at endringer 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, som brukes i tegneprogrammer og spillkart, egner seg naturlig for rekursjon. Start med en celle, marker den, og fyll deretter rekursivt alle naboer som ikke er besøkt. Rekursjonen avsluttes når den møter en grense eller en celle som allerede er besøkt.
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 2Vær oppmerksom på stackdybden
Lua sin standardkallstack har en begrensning, vanligvis rundt 200 nivåer for kall som ikke er tail calls. Dyp rekursjon uten tail calls fører til feilen «stack overflow». Løsninger er å gjøre rekursjonen om til tail-rekursjon, bruke en eksplisitt stack (tabell) eller bruke coroutines for store iterative oppgaver.
-- 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 overflowRask kontroll
Hvilket av følgende er et korrekt tail call i Lua?
Oppsummering: Rekursjon
Oppsummering:
- Alle rekursive funksjoner trenger et basistilfelle og et rekursivt tilfelle
- Tail calls, der den siste handlingen er et kall, optimaliseres av Lua og bruker O(1) plass på stacken
- Memoization gjør eksponentiell rekursjon lineær
- Gjensidig rekursjon krever forhåndsdeklarasjoner
- Dyp rekursjon i trær og grafer er naturlig, men følg med på stackdybden ved kall som ikke er tail calls
Lær deg Lua med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 40
- Leksjoner
- 159
Ofte stilte spørsmål
Er leksjonen «Rekursjon i Lua» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien Lua Academy, inkludert «Rekursjon i Lua», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i Lua Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Rekursjon i Lua»?
Implementer rekursive algoritmer og forstå Lua sin optimalisering av haleanrop. Du øver på Lua Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Lua Academy?
Ingen tidligere erfaring er nødvendig. Lua Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Rekursjon i Lua»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Lua Academy-leksjonen?
Ja. Alle Lua Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.