Lua Academy · Oppitunti

Rekursio Luassa

Toteuttakaa rekursiivisia algoritmeja ja perehtykää Luan häntärekursio-optimointiin.

Oppitunti 4/412 vaihetta

Rekursio Luassa on ilmainen Lua Academy-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu Lua Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Lua Academy-kurssilla on yhteensä 4 oppituntia.

Mitä rekursio on?

Rekursiossa funktio kutsuu itseään ratkaistakseen saman ongelman pienemmän tapauksen. Jokainen rekursiivinen funktio tarvitsee perustapauksen (milloin suoritus lopetetaan) ja rekursiivisen tapauksen (milloin ongelmaa pienennetään). Ilman perustapausta rekursio aiheuttaa pinon ylivuodon.

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!

Kertoma

Kertoma on klassinen rekursioesimerkki: n! = n × (n-1)!, ja perustapaus on 0! = 1. Jokainen kutsu pienentää n-arvoa yhdellä, kunnes perustapaus saavutetaan. Tulokset purkautuvat kutsupinossa takaisin ylöspäin ja kertovat samalla toisensa.

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))  -- 3628800

Fibonaccin lukujono

Fibonaccin lukujono on toinen klassinen esimerkki: fib(n) = fib(n-1) + fib(n-2). Naiivi rekursio on eksponentiaalinen, koska se laskee samat arvot toistuvasti uudelleen. Seuraavaksi tarkastelemme muistiointia ratkaisuna, mutta ensin perusmuotoa.

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 55

Muistioitu rekursio

Muistioinnissa aiemmin lasketut tulokset tallennetaan välimuistiin taulukossa. Tarkistakaa välimuisti ensin jokaisen kutsun yhteydessä. Jos arvo löytyy, palauttakaa se heti. Muussa tapauksessa laskekaa arvo ja tallentakaa se. Näin Fibonaccin eksponentiaalinen suoritusaika muuttuu lineaariseksi.

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!)

Häntäkutsujen optimointi

Lua suorittaa häntäkutsujen optimointia (TCO): kun funktion viimeinen toiminto on toisen funktion kutsu, Lua käyttää nykyistä pinokehystä uudelleen. Tämän ansiosta häntärekursiiviset funktiot käyttävät pinotilaa O(1). Kaikki rekursio ei ole häntärekursiivista — kutsun on oltava funktion viimeinen toiminto.

-- 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 overflow

Puun läpikäynti

Rekursio ilmaisee puun läpikäynnin luontevasti. Puu on taulukko, jolla on value-, left- ja right-kentät. Esijärjestys-, sisäjärjestys- ja jälkijärjestysläpikäynnit eroavat toisistaan vain siinä, milloin arvo käsitellään suhteessa rekursiivisiin kutsuihin.

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

Keskinäinen rekursio

Kaksi funktiota voi kutsua toisiaan (keskinäinen rekursio). Luassa tarvitaan ennakkoilmoitukset: ilmoittakaa paikalliset muuttujat ensin ja sijoittakaa funktiot niihin vasta sen jälkeen. Näin kumpikin funktio voi viitata toisen muuttujaan, joka on jo näkyvyysalueella.

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))    -- true

Rekursiivinen syväkopio

Rekursio sopii erinomaisesti sisäkkäisten rakenteiden käsittelyyn. Taulukon syväkopiointi tarkoittaa sen sisällön kopioimista ja kaikkien sisäkkäisten taulukoiden rekursiivista kopioimista, jotta kopion muuttaminen ei vaikuta alkuperäiseen.

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)

Tulvatäyttöalgoritmi

Tulvatäyttö (jota käytetään maalausohjelmissa ja pelien kartoissa) on luontevasti rekursiivinen. Aloittakaa solusta, merkitkää se ja täyttäkää sitten rekursiivisesti jokainen käymätön naapuri. Rekursio päättyy, kun saavutetaan reuna tai jo käsitelty solu.

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  2

Pinon syvyyden huomioiminen

Luan oletusarvoinen kutsupino on rajallinen (tyypillisesti noin 200 tasoa muissa kuin häntäkutsuissa). Syvä rekursio, joka ei ole häntärekursiota, aiheuttaa "stack overflow" -virheen. Ratkaisuja ovat muuttaminen häntärekursioksi, eksplisiittisen pinon (taulukon) käyttäminen tai korutiinien käyttäminen suuriin iteroiviin tehtäviin.

-- 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 overflow

Pikatarkistus

Mikä seuraavista on Luassa oikea häntäkutsu?

Vastaa interaktiivisessa oppitunnissa

Kertaus: Rekursio

Yhteenveto:

Jokainen rekursiivinen funktio tarvitsee perustapauksen ja rekursiivisen tapauksen
Lua optimoi häntäkutsut (viimeinen toiminto on kutsu) — pino vie tilaa O(1)
Muistiointi muuttaa eksponentiaalisen rekursion lineaariseksi
Keskinäinen rekursio edellyttää ennakkoilmoituksia
Syvä rekursio puissa ja graafeissa on luontevaa; tarkkailkaa pinon syvyyttä muiden kuin häntäkutsujen yhteydessä

Aloita maksutta

Opi Lua tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 40
Oppitunnit: 159

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Rekursio Luassa” ilmainen?

Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa Lua Academy-oppimispolun 3 oppituntia, myös oppitunnin “Rekursio Luassa”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Lua Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Rekursio Luassa”?

Toteuttakaa rekursiivisia algoritmeja ja perehtykää Luan häntärekursio-optimointiin. Harjoittelet Lua Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Lua Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Lua Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Rekursio Luassa”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Lua Academy-oppitunnilla?

Kyllä. Jokainen Lua Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Lua Academy