Rekursi dalam Lua
Laksanakan algoritma rekursif dan fahami pengoptimuman panggilan ekor Lua.
Rekursi dalam Lua ialah pelajaran Lua Academy percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Lua Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Lua Academy merangkumi sejumlah 4 pelajaran.
Apakah Rekursi?
Rekursi berlaku apabila fungsi memanggil dirinya sendiri untuk menyelesaikan contoh yang lebih kecil bagi masalah yang sama. Setiap fungsi rekursif memerlukan kes asas, iaitu keadaan untuk berhenti, dan kes rekursif, iaitu keadaan yang mengurangkan masalah. Tanpa kes asas, rekursi menyebabkan limpahan tindanan.
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 ialah contoh rekursi klasik: n! = n × (n-1)! dengan kes asas 0! = 1. Setiap panggilan mengurangkan n sebanyak 1 sehingga mencapai kes asas. Hasilnya "terungkai" kembali ke atas tindanan panggilan sambil didarabkan.
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
Siri Fibonacci ialah satu lagi contoh klasik: fib(n) = fib(n-1) + fib(n-2). Rekursi naif mempunyai kerumitan eksponen — ia mengira semula nilai yang sama berulang kali. Kita akan melihat pemokean sebagai penyelesaian, tetapi terlebih dahulu lihat bentuk asasnya.
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 55Rekursi dengan Pemokean
Pemokean menyimpan hasil yang telah dikira sebelum ini dalam jadual. Pada setiap panggilan, semak cache terlebih dahulu. Jika nilainya ada, kembalikannya serta-merta. Jika tiada, kirakan dan simpan nilainya. Ini menukarkan Fibonacci bermasa eksponen kepada masa 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!)Pengoptimuman Panggilan Ekor
Lua melaksanakan pengoptimuman panggilan ekor (TCO): apabila tindakan terakhir suatu fungsi ialah panggilan kepada fungsi lain, Lua menggunakan semula bingkai tindanan semasa. Ini menyebabkan fungsi rekursif ekor menggunakan ruang tindanan O(1). Tidak semua rekursi ialah rekursi ekor — panggilan itu mestilah perkara 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 overflowRentasan Pepohon
Rekursi menyatakan rentasan pepohon secara semula jadi. Pepohon ialah jadual dengan medan value, left, dan right. Rentasan prapesanan, dalam pesanan, dan pascapesanan hanya berbeza dari segi masa nilai diproses berbanding panggilan 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 7Rekursi Bersama
Dua fungsi boleh memanggil satu sama lain (rekursi bersama). Dalam Lua, anda memerlukan pengisytiharan ke hadapan: isytiharkan pemboleh ubah tempatan dahulu, kemudian tetapkan fungsi kepadanya. Dengan cara ini, setiap fungsi boleh merujuk pemboleh ubah fungsi yang satu lagi, yang sudah berada dalam skop.
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)) -- trueSalinan Mendalam Rekursif
Rekursi amat sesuai untuk operasi pada struktur bersarang. Menyalin jadual secara mendalam bermaksud menyalin kandungannya dan menyalin secara rekursif mana-mana jadual bersarang, supaya pengubahsuaian salinan tidak menjejaskan asalnya.
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)Algoritma Isian Banjir
Isian banjir, yang digunakan dalam program melukis dan peta permainan, sememangnya sesuai dilaksanakan secara rekursif. Bermula daripada suatu sel, tandakannya, kemudian isi setiap jiran yang belum dilawati secara rekursif. Rekursi berhenti apabila menemui sempadan atau sel yang telah dilawati.
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 2Kesedaran tentang Kedalaman Tindanan
Tindanan panggilan lalai Lua adalah terhad, biasanya sekitar 200 aras untuk panggilan bukan ekor. Rekursi bukan ekor yang mendalam menyebabkan ralat "limpahan tindanan". Penyelesaiannya termasuk menukarkannya kepada rekursi ekor, menggunakan tindanan eksplisit (jadual), atau menggunakan korutin untuk tugas beriterasi 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 overflowSemakan Pantas
Antara berikut, yang manakah panggilan ekor yang betul dalam Lua?
Ulang Kaji: Rekursi
Ringkasan:
- Setiap fungsi rekursif memerlukan kes asas dan kes rekursif
- Panggilan ekor, iaitu tindakan terakhir ialah panggilan, dioptimumkan oleh Lua — tindanan O(1)
- Pemokean menukarkan rekursi eksponen kepada linear
- Rekursi bersama memerlukan pengisytiharan ke hadapan
- Rekursi mendalam pada pepohon/graf adalah semula jadi; awasi kedalaman tindanan untuk panggilan bukan ekor
Pelajari Lua dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 40
- Pelajaran
- 159
Soalan Lazim
Adakah pelajaran “Rekursi dalam Lua” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran Lua Academy, termasuk “Rekursi dalam Lua”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus Lua Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Rekursi dalam Lua”?
Laksanakan algoritma rekursif dan fahami pengoptimuman panggilan ekor Lua. Anda berlatih Lua Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Lua Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Lua Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Rekursi dalam Lua” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Lua Academy ini?
Ya. Setiap pelajaran Lua Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.