Lua Academy · Pelajaran

Rekursi dalam Lua

Implementasikan algoritme rekursif dan pahami optimisasi pemanggilan ekor Lua.

Rekursi dalam Lua adalah pelajaran Lua Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Lua Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Lua Academy mencakup 4 pelajaran total.

Apa Itu Rekursi?

Rekursi adalah ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan kasus yang lebih kecil dari masalah yang sama. Setiap fungsi rekursif memerlukan kasus dasar (tempat fungsi berhenti) dan kasus rekursif (tempat masalah diperkecil). Tanpa kasus dasar, rekursi menyebabkan luapan tumpukan.

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!

Faktorial

Faktorial adalah contoh klasik rekursi: n! = n × (n-1)! dengan kasus dasar 0! = 1. Setiap pemanggilan mengurangi n sebesar 1 hingga mencapai kasus dasar. Hasilnya "dibuka kembali" ke atas dalam tumpukan pemanggilan, sambil dikalikan.

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

Fibonacci

Barisan Fibonacci adalah contoh klasik lainnya: fib(n) = fib(n-1) + fib(n-2). Rekursi naif bersifat eksponensial — nilai yang sama dihitung berulang kali. Kita akan melihat memoization sebagai solusinya, tetapi terlebih dahulu membahas bentuk dasarnya.

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

Rekursi dengan Memoisasi

Memoisasi menyimpan hasil yang telah dihitung sebelumnya dalam sebuah tabel. Pada setiap pemanggilan, periksa cache terlebih dahulu. Jika nilainya ada, segera kembalikan nilai tersebut. Jika tidak, hitung dan simpan nilainya. Dengan demikian, waktu Fibonacci yang semula eksponensial menjadi linear.

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

Optimisasi Pemanggilan Ekor

Lua melakukan optimisasi pemanggilan ekor (TCO): ketika tindakan terakhir sebuah fungsi adalah pemanggilan ke fungsi lain, Lua menggunakan kembali bingkai tumpukan saat ini. Hal ini membuat fungsi rekursif-ekor menggunakan ruang tumpukan O(1). Tidak semua rekursi merupakan rekursi-ekor — pemanggilan tersebut harus menjadi hal terakhir dalam fungsi.

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

Penelusuran Pohon

Rekursi secara alami menyatakan penelusuran pohon. Pohon adalah tabel dengan field value, left, dan right. Penelusuran preorder, inorder, dan postorder hanya berbeda dalam waktu pemrosesan nilai relatif terhadap pemanggilan rekursif.

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

Rekursi Saling

Dua fungsi dapat saling memanggil (rekursi saling). Dalam Lua, Anda memerlukan deklarasi ke depan: deklarasikan variabel lokal terlebih dahulu, lalu tetapkan fungsi-fungsinya. Dengan cara ini, setiap fungsi dapat merujuk ke variabel fungsi lainnya, yang sudah berada dalam cakupan.

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

Salinan Mendalam Rekursif

Rekursi sangat sesuai untuk operasi pada struktur bertingkat. Menyalin tabel secara mendalam berarti menyalin isinya dan menyalin secara rekursif setiap tabel bersarang (sehingga perubahan pada salinan tidak memengaruhi aslinya).

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)

Algoritme Pengisian Banjir

Pengisian banjir (digunakan dalam program menggambar dan peta permainan) secara alami bersifat rekursif. Mulai dari sebuah sel, tandai sel tersebut, lalu isi setiap tetangga yang belum dikunjungi secara rekursif. Rekursi berakhir ketika mencapai batas atau sel yang sudah dikunjungi.

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

Kesadaran akan Kedalaman Tumpukan

Tumpukan pemanggilan bawaan Lua memiliki batas (biasanya sekitar 200 tingkat untuk pemanggilan non-ekor). Rekursi non-ekor yang dalam menyebabkan galat "luapan tumpukan". Solusinya: ubah menjadi rekursi-ekor, gunakan tumpukan eksplisit (tabel), atau gunakan coroutine untuk tugas iteratif yang besar.

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

Pemeriksaan Cepat

Manakah dari berikut ini yang merupakan pemanggilan ekor yang benar dalam Lua?

Ringkasan: Rekursi

Ringkasan:

Setiap fungsi rekursif memerlukan kasus dasar dan kasus rekursif
Pemanggilan ekor (tindakan terakhir adalah pemanggilan) dioptimalkan oleh Lua — tumpukan O(1)
Memoisasi mengubah rekursi eksponensial menjadi linear
Rekursi saling memerlukan deklarasi ke depan
Rekursi dalam pada pohon/graf bersifat alami; perhatikan kedalaman tumpukan untuk pemanggilan non-ekor

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Rekursi dalam Lua” gratis?

Ya — teks lengkap “Rekursi dalam Lua” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Lua Academy, upgrade ke CoddyKit PRO. Kursus Lua Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Rekursi dalam Lua”?

Implementasikan algoritme rekursif dan pahami optimisasi pemanggilan ekor Lua. Kamu berlatih Lua Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Lua Academy?

Tidak diperlukan pengalaman sebelumnya. Lua Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Rekursi dalam Lua” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Lua Academy ini?

Ya. Setiap pelajaran Lua Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Lua Academy