Lua में पुनरावर्तन
पुनरावर्ती एल्गोरिदम लागू करें और Lua के टेल-कॉल अनुकूलन को समझें।
Lua में पुनरावर्तन, CoddyKit पर Lua Academy का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह Lua Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Lua Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
पुनरावर्तन क्या है
पुनरावर्तन तब होता है जब कोई फ़ंक्शन उसी समस्या के छोटे रूप को हल करने के लिए स्वयं को कॉल करता है। हर पुनरावर्ती फ़ंक्शन को एक आधार स्थिति चाहिए, जहाँ वह रुकता है, और एक पुनरावर्ती स्थिति चाहिए, जहाँ वह समस्या को छोटा करता है। आधार स्थिति के बिना पुनरावर्तन स्टैक ओवरफ़्लो का कारण बनता है।
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!फैक्टोरियल
फैक्टोरियल पुनरावर्तन का पारंपरिक उदाहरण है: n! = n × (n-1)!, जिसकी आधार स्थिति 0! = 1 है। आधार स्थिति तक पहुँचने तक हर कॉल n को 1 घटाती है। परिणाम कॉल स्टैक में ऊपर की ओर लौटते हैं और लौटते समय गुणा करते जाते हैं।
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फिबोनाची
फिबोनाची अनुक्रम एक और पारंपरिक उदाहरण है: fib(n) = fib(n-1) + fib(n-2)। सरल पुनरावर्तन घातीय होता है—यह समान मानों की बार-बार गणना करता है। इसके समाधान के रूप में हम स्मृति-संग्रहण देखेंगे, लेकिन पहले मूल रूप समझेंगे।
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स्मृति-संग्रहित पुनरावर्तन
स्मृति-संग्रहण पहले से गणना किए गए परिणामों को तालिका में कैश करता है। हर कॉल पर पहले कैश जाँचें। यदि मान वहाँ है, तो उसे तुरंत लौटा दें। अन्यथा, उसकी गणना करके संग्रहीत करें। इससे फिबोनाची की घातीय समय-जटिलता रैखिक हो जाती है।
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!)टेल कॉल अनुकूलन
Lua टेल कॉल अनुकूलन (TCO) करता है: जब फ़ंक्शन की अंतिम क्रिया किसी दूसरे फ़ंक्शन को कॉल करना होती है, तो Lua वर्तमान स्टैक फ़्रेम का पुनः उपयोग करता है। इससे टेल-पुनरावर्ती फ़ंक्शन O(1) स्टैक स्थान का उपयोग करते हैं। हर पुनरावर्तन टेल-पुनरावर्ती नहीं होता—कॉल फ़ंक्शन में अंतिम क्रिया होनी चाहिए।
-- 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ट्री परिभ्रमण
पुनरावर्तन ट्री परिभ्रमण को स्वाभाविक रूप से व्यक्त करता है। ट्री एक तालिका होती है जिसमें value, left और right फ़ील्ड होते हैं। प्रीऑर्डर, इनऑर्डर और पोस्टऑर्डर परिभ्रमण केवल इस बात में अलग होते हैं कि पुनरावर्ती कॉल के संबंध में मान को कब संसाधित किया जाता है।
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पारस्परिक पुनरावर्तन
दो फ़ंक्शन एक-दूसरे को कॉल कर सकते हैं, इसे पारस्परिक पुनरावर्तन कहते हैं। Lua में आपको अग्रिम घोषणाएँ करनी होती हैं: पहले स्थानीय चरों की घोषणा करें, फिर फ़ंक्शन असाइन करें। इस प्रकार हर फ़ंक्शन दूसरे के चर का संदर्भ दे सकता है, जो पहले से ही दायरे में होता है।
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पुनरावर्ती deepCopy
नेस्टेड संरचनाओं पर कार्यों के लिए पुनरावर्तन आदर्श है। किसी तालिका की गहरी प्रतिलिपि बनाने का अर्थ है उसकी सामग्री की प्रतिलिपि बनाना और किसी भी नेस्टेड तालिका की पुनरावर्ती प्रतिलिपि बनाना, ताकि प्रतिलिपि में बदलाव से मूल प्रभावित न हो।
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)फ्लड फ़िल एल्गोरिदम
फ्लड फ़िल, जिसका उपयोग पेंट प्रोग्राम और गेम मानचित्रों में होता है, स्वाभाविक रूप से पुनरावर्ती है। किसी सेल से शुरू करके उसे चिह्नित करें, फिर हर ऐसे पड़ोसी को पुनरावर्ती रूप से भरें जिसे अभी देखा नहीं गया है। सीमा या पहले से देखे गए सेल पर पहुँचने पर पुनरावर्तन समाप्त हो जाता है।
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स्टैक गहराई की जानकारी
Lua का डिफ़ॉल्ट कॉल स्टैक सीमित होता है, सामान्यतः गैर-टेल कॉल के लिए लगभग 200 स्तर। गहरा गैर-टेल पुनरावर्तन "स्टैक ओवरफ़्लो" त्रुटि उत्पन्न करता है। समाधान हैं: इसे टेल पुनरावर्तन में बदलें, स्पष्ट स्टैक (तालिका) का उपयोग करें, या बड़े पुनरावृत्त कार्यों के लिए कोरूटीन का उपयोग करें।
-- 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त्वरित जाँच
निम्नलिखित में से कौन-सी Lua में उचित टेल कॉल है?
पुनरावलोकन: पुनरावर्तन
सारांश:
- हर पुनरावर्ती फ़ंक्शन को आधार स्थिति और पुनरावर्ती स्थिति चाहिए
- टेल कॉल, यानी अंतिम क्रिया के रूप में की गई कॉल, Lua द्वारा अनुकूलित की जाती हैं—O(1) स्टैक
- स्मृति-संग्रहण घातीय पुनरावर्तन को रैखिक में बदल देता है
- पारस्परिक पुनरावर्तन के लिए अग्रिम घोषणाएँ आवश्यक हैं
- ट्री या ग्राफ़ पर गहरा पुनरावर्तन स्वाभाविक है; गैर-टेल कॉल में स्टैक गहराई पर ध्यान दें
एआई शिक्षक के साथ Lua सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 40
- पाठ
- 159
अक्सर पूछे जाने वाले प्रश्न
क्या “Lua में पुनरावर्तन” पाठ निःशुल्क है?
हाँ — Lua Academy अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “Lua में पुनरावर्तन” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। Lua Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Lua में पुनरावर्तन” में मैं क्या सीखूँगा?
पुनरावर्ती एल्गोरिदम लागू करें और Lua के टेल-कॉल अनुकूलन को समझें। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Lua Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या Lua Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Lua Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।
“Lua में पुनरावर्तन” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस Lua Academy पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर Lua Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- फ़ंक्शन परिभाषित करना और कॉल करना
- एकाधिक वापसी मान
- Varargs और ... ऑपरेटर
- Lua में पुनरावर्तन