Lua'da Özyineleme
Özyinelemeli algoritmalar uygulayın ve Lua'nın kuyruk çağrısı optimizasyonunu anlayın.
Lua'da Özyineleme, CoddyKit'te ücretsiz bir Lua Academy dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Lua Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Lua Academy kursu toplamda 4 dersten oluşur.
Özyineleme Nedir?
Özyineleme, bir fonksiyonun aynı sorunun daha küçük bir örneğini çözmek için kendisini çağırmasıdır. Her özyinelemeli fonksiyonun bir temel durumu (durduğu nokta) ve bir özyinelemeli durumu (sorunu küçülttüğü nokta) olması gerekir. Temel durum olmazsa özyineleme yığın taşmasına neden olur.
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!Faktöriyel
Faktöriyel, özyinelemenin klasik örneğidir: temel durum 0! = 1 olmak üzere n! = n × (n-1)!. Her çağrı, temel duruma ulaşılana kadar n değerini 1 azaltır. Sonuçlar çağrı yığını boyunca geri açılırken çarpılmaya devam eder.
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 dizisi de başka bir klasik örnektir: fib(n) = fib(n-1) + fib(n-2). Saf özyineleme üstel zamanlıdır; aynı değerleri tekrar tekrar hesaplar. Çözüm olarak anımsamayı göreceğiz, ancak önce temel biçime bakalım.
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 55Anısmalı Özyineleme
Anımsama, daha önce hesaplanan sonuçları bir tabloda önbelleğe alır. Her çağrıda önce önbelleği kontrol edin. Değer oradaysa hemen döndürün. Aksi halde değeri hesaplayıp saklayın. Bu, Fibonacci hesabını üstel zamandan doğrusal zamana dönüştürü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!)Kuyruk Çağrısı Optimizasyonu
Lua, kuyruk çağrısı optimizasyonu (TCO) uygular: bir fonksiyonun son işlemi başka bir fonksiyona yapılan çağrı olduğunda Lua, geçerli yığın çerçevesini yeniden kullanır. Bu, kuyruk özyinelemeli fonksiyonların O(1) yığın alanı kullanmasını sağlar. Her özyineleme kuyruk özyinelemesi değildir — çağrı, fonksiyondaki son işlem olmalıdır.
-- 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 overflowAğaç Gezinme
Özyineleme, ağaç gezinmesini doğal biçimde ifade eder. Ağaç; value, left ve right alanlarına sahip bir tablodur. Ön sıralı, ara sıralı ve son sıralı gezinmeler yalnızca değerin özyinelemeli çağrılara göre ne zaman işlendiği bakımından farklıdır.
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 7Karşılıklı Özyineleme
İki fonksiyon birbirini çağırabilir (karşılıklı özyineleme). Lua'da ileri bildirimlere ihtiyacınız vardır: önce yerel değişkenleri bildirin, ardından fonksiyonları atayın. Böylece her fonksiyon, diğerinin zaten kapsam içinde bulunan değişkenine başvurabilir.
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Özyinelemeli Derin Kopya
Özyineleme, iç içe yapıların işlemleri için idealdir. Bir tabloyu derin kopyalamak, içeriğini kopyalamak ve iç içe tabloları da özyinelemeli olarak kopyalamak demektir (böylece kopyayı değiştirmek özgün tabloyu etkilemez).
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)Taşma Doldurma Algoritması
Taşma doldurma (boyama programlarında ve oyun haritalarında kullanılır) doğal olarak özyinelemelidir. Bir hücreden başlayarak hücreyi işaretleyin, ardından ziyaret edilmemiş her komşuyu özyinelemeli olarak doldurun. Özyineleme, sınırlara veya daha önce ziyaret edilmiş hücrelere ulaştığında sona erer.
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 2Yığın Derinliğinin Farkında Olma
Lua'nın varsayılan çağrı yığını sınırlıdır (kuyruk çağrısı olmayan çağrılar için genellikle yaklaşık 200 seviye). Derin kuyruk çağrısı olmayan özyineleme, "stack overflow" hatasına neden olur. Çözümler: kuyruk özyinelemesine dönüştürmek, açık bir yığın (tablo) kullanmak veya büyük yinelemeli görevler için eş yordamlar kullanmaktır.
-- 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 overflowKısa Kontrol
Aşağıdakilerden hangisi Lua'da doğru bir kuyruk çağrısıdır?
Özet: Özyineleme
Özet:
- Her özyinelemeli fonksiyonun bir temel duruma ve bir özyinelemeli duruma ihtiyacı vardır
- Kuyruk çağrıları (son işlem bir çağrıdır) Lua tarafından optimize edilir — O(1) yığın
- Anımsama, üstel özyinelemeyi doğrusal zamana dönüştürür
- Karşılıklı özyineleme ileri bildirimler gerektirir
- Ağaçlar/graflar üzerinde derin özyineleme doğaldır; kuyruk çağrısı olmayan çağrılarda yığın derinliğine dikkat edin
Sıkça Sorulan Sorular
“Lua'da Özyineleme” dersi ücretsiz mi?
Evet — “Lua'da Özyineleme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Lua Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Lua Academy kursu toplamda 4 dersten oluşur.
“Lua'da Özyineleme” dersinde ne öğreneceğim?
Özyinelemeli algoritmalar uygulayın ve Lua'nın kuyruk çağrısı optimizasyonunu anlayın. Lua Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Lua Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Lua Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Lua'da Özyineleme” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Lua Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Lua Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- İşlev Tanımlama ve Çağırma
- Birden Çok Dönüş Değeri
- Değişken Sayıda Bağımsız Değer ve ... Operatörü
- Lua'da Özyineleme