Lua Academy · Lekcja

Rekurencja w Lua

Proszę implementować algorytmy rekurencyjne i poznać optymalizację wywołań końcowych w Lua.

Rekurencja w Lua to bezpłatna lekcja Lua Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Lua Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Lua Academy zawiera 4 lekcji w sumie.

Czym jest rekurencja?

Rekurencja zachodzi wtedy, gdy funkcja wywołuje samą siebie, aby rozwiązać mniejszy przypadek tego samego problemu. Każda funkcja rekurencyjna potrzebuje przypadku bazowego (w którym się zatrzymuje) oraz przypadku rekurencyjnego (w którym zmniejsza problem). Bez przypadku bazowego rekurencja prowadzi do przepełnienia stosu.

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!

Silnia

Silnia to klasyczny przykład rekurencji: n! = n × (n-1)!, a przypadek bazowy to 0! = 1. Każde wywołanie zmniejsza n o 1 aż do osiągnięcia przypadku bazowego. Wyniki są następnie „rozwijane” w górę stosu wywołań, po drodze mnożąc wartości.

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

Ciąg Fibonacciego

Ciąg Fibonacciego to kolejny klasyczny przykład: fib(n) = fib(n-1) + fib(n-2). Naiwna rekurencja ma wykładniczą złożoność, ponieważ wielokrotnie oblicza te same wartości. Zobaczymy, jak naprawić ten problem za pomocą zapamiętywania wyników, ale najpierw poznajmy podstawową postać.

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

Rekurencja z zapamiętywaniem wyników

Zapamiętywanie wyników przechowuje wcześniej obliczone rezultaty w tabeli. Przy każdym wywołaniu najpierw sprawdź pamięć podręczną. Jeśli wartość już tam jest, natychmiast ją zwróć. W przeciwnym razie oblicz ją i zapisz. Dzięki temu obliczanie ciągu Fibonacciego ma złożoność liniową zamiast wykładniczej.

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

Optymalizacja wywołań ogonowych

Lua wykonuje optymalizację wywołań ogonowych (TCO): gdy ostatnim działaniem funkcji jest wywołanie innej funkcji, Lua ponownie wykorzystuje bieżącą ramkę stosu. Dzięki temu funkcje rekurencyjne z wywołaniem ogonowym zajmują O(1) miejsca na stosie. Nie każda rekurencja jest ogonowa — wywołanie musi być ostatnią czynnością w funkcji.

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

Przechodzenie drzewa

Rekurencja naturalnie opisuje przechodzenie drzewa. Drzewo jest tabelą z polami value, left i right. Przechodzenie preorder, inorder i postorder różni się tylko momentem przetworzenia wartości względem wywołań rekurencyjnych.

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

Rekurencja wzajemna

Dwie funkcje mogą wywoływać się nawzajem (rekurencja wzajemna). W Lua potrzebne są deklaracje wyprzedzające: najpierw należy zadeklarować zmienne lokalne, a następnie przypisać do nich funkcje. Dzięki temu każda funkcja może odwoływać się do zmiennej drugiej funkcji, która jest już w jej zakresie.

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

Rekurencyjne głębokie kopiowanie

Rekurencja doskonale nadaje się do operacji na zagnieżdżonych strukturach. Głębokie kopiowanie tabeli oznacza skopiowanie jej zawartości oraz rekurencyjne skopiowanie wszystkich zagnieżdżonych tabel, dzięki czemu modyfikowanie kopii nie wpływa na oryginał.

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)

Algorytm wypełniania obszaru

Wypełnianie obszaru (używane w programach graficznych i mapach gier) w naturalny sposób realizuje się rekurencyjnie. Rozpoczynając od komórki, oznacz ją, a następnie rekurencyjnie wypełnij każdego nieodwiedzonego sąsiada. Rekurencja kończy się po dotarciu do granic lub wcześniej odwiedzonych komórek.

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

Kontrola głębokości stosu

Domyślny stos wywołań Lua jest ograniczony (zwykle do około 200 poziomów dla wywołań innych niż ogonowe). Głęboka rekurencja bez wywołań ogonowych powoduje błąd „stack overflow”. Rozwiązania to: przekształcenie jej w rekurencję ogonową, użycie jawnego stosu (tabeli) albo użycie coroutine w przypadku dużych zadań iteracyjnych.

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

Szybkie sprawdzenie

Które z poniższych wywołań jest poprawnym wywołaniem ogonowym w Lua?

Powtórzenie: rekurencja

Podsumowanie:

Każda funkcja rekurencyjna potrzebuje przypadku bazowego i rekurencyjnego
Wywołania ogonowe (gdy ostatnim działaniem jest wywołanie) są optymalizowane przez Lua — stos ma rozmiar O(1)
Zapamiętywanie wyników przekształca rekurencję o wykładniczej złożoności w liniową
Rekurencja wzajemna wymaga deklaracji wyprzedzających
Głęboka rekurencja w drzewach i grafach jest naturalna, ale w przypadku wywołań nieogonowych należy kontrolować głębokość stosu

Często zadawane pytania

Czy lekcja „Rekurencja w Lua” jest bezpłatna?

Tak — pełny tekst „Rekurencja w Lua” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Lua Academy, przejdź na CoddyKit PRO. Kurs Lua Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Rekurencja w Lua”?

Proszę implementować algorytmy rekurencyjne i poznać optymalizację wywołań końcowych w Lua. Ćwiczysz Lua Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Lua Academy?

Nie wymagamy żadnego doświadczenia. Lua Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Rekurencja w Lua”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Lua Academy?

Tak. Każda lekcja Lua Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Lua Academy