पुनरावर्ती बनाम पुनरावृत्तीय संतुलन
पुनरावर्ती factorial और Fibonacci को पुनरावृत्त लूप में बदलिए तथा समझाइए कि Python की पुनरावृत्ति सीमा और स्टैक आकार कब पुनरावृत्तीय तरीका बेहतर बनाते हैं।
पुनरावर्ती बनाम पुनरावृत्तीय संतुलन, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
पुनरावर्ती-पुनरावृत्तिमूलक द्वैत
हर वह एल्गोरिदम जिसे पुनरावर्ती रूप में लिखा जा सकता है, पुनरावृत्तिमूलक रूप में भी लिखा जा सकता है, और इसके विपरीत भी। पुनरावर्ती रूप अक्सर समस्या की गणितीय परिभाषा को अधिक निकटता से दर्शाता है, जबकि पुनरावृत्तिमूलक रूप मेमोरी पर स्पष्ट नियंत्रण देता है और स्टैक अतिप्रवाह के जोखिम से बचाता है। दोनों में से किसी एक को चुनना पठनीयता, गहराई की सीमाओं और प्रदर्शन संबंधी आवश्यकताओं पर आधारित व्यावहारिक निर्णय है।
साक्षात्कारों में दोनों रूप प्रस्तुत कर पाना और उनके लाभ-हानि समझा पाना दक्षता का मजबूत संकेत है।
factorial: पुनरावर्ती बनाम पुनरावृत्तिमूलक
factorial इसका आदर्श उदाहरण है। पुनरावर्ती रूप गणितीय परिभाषा n! = n × (n-1)! को सीधे व्यक्त करता है। n लंबित वापसी मानों के कारण यह O(n) स्टैक स्थान का उपयोग करता है। पुनरावृत्तिमूलक रूप 1 से n तक चक्र चलाता है और O(1) स्थान का उपयोग करता है। n = 1000 पर पुनरावर्ती रूप पायथन की डिफ़ॉल्ट सीमा तक पहुँच जाता है; पुनरावृत्तिमूलक रूप मनमाने बड़े n को संभाल सकता है।
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)फ़िबोनाची: घातीय बनाम रैखिक
सरल पुनरावर्ती फ़िबोनाची का समय O(2^n) है — बड़े n के लिए यह अत्यंत धीमा होता है। पुनरावृत्तिमूलक रूप का समय O(n) और स्थान O(1) है। मेमोइज़्ड पुनरावर्तन (अगले पाठ में) का समय भी O(n) है, लेकिन मेमो शब्दकोश और O(n) स्टैक के कारण स्थान O(n) है। फ़िबोनाची के लिए सभी मानदंडों पर पुनरावृत्तिमूलक तरीका सर्वोत्तम है। n = 50 पर सरल पुनरावर्तन में कई सेकंड लगते हैं; पुनरावृत्तिमूलक रूप में माइक्रोसेकंड लगते हैं।
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nवृक्ष का भ्रमण: पुनरावर्ती बनाम पुनरावृत्तिमूलक
पुनरावर्ती वृक्ष-भ्रमण स्वाभाविक रूप से साफ़ होता है, क्योंकि वृक्ष की संरचना पुनरावर्तन से मेल खाती है। लेकिन बहुत अधिक तिरछे वृक्ष के लिए (जो मूलतः एक लिंक्ड सूची जैसा होता है), पुनरावर्तन की गहराई वृक्ष की ऊँचाई के बराबर, यानी O(n), हो जाती है और स्टैक के भर जाने का जोखिम रहता है। स्पष्ट स्टैक का उपयोग करने वाले पुनरावृत्तिमूलक संस्करण में गहराई की कोई सीमा नहीं होती और स्टैक का आकार कॉल स्टैक के बजाय हीप पर बढ़ सकता है।
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]मर्ज सॉर्ट: पुनरावर्ती बनाम पुनरावृत्तिमूलक (नीचे-से-ऊपर)
मर्ज सॉर्ट स्वाभाविक रूप से पुनरावर्ती होता है (विभाजित करें, पुनरावर्तन करें, विलय करें)। पुनरावृत्तिमूलक नीचे-से-ऊपर मर्ज सॉर्ट पुनरावर्तन से पूरी तरह बचता है: 1 आकार की उप-सरणियों से शुरू करें, आस-पास के युग्मों का विलय करके 2 आकार की उप-सरणियाँ बनाएँ, फिर 4 आकार की, और इसी तरह हर चरण में उप-सरणी का आकार दोगुना करते जाएँ। नीचे-से-ऊपर मर्ज सॉर्ट में समय O(n log n), स्थान O(n) (विलय बफ़र के लिए) और स्टैक स्थान O(1) होता है।
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]जब पुनरावर्तन स्पष्ट रूप से बेहतर हो
पुनरावर्तन तब सबसे उपयोगी होता है जब समस्या में वृक्ष-जैसी संरचना हो, जो सीधे कॉल ग्राफ से मेल खाती हो, आधार मामले स्वाभाविक हों और गहराई सीमित हो (संतुलित वृक्षों तथा विभाजन-और-विजय विधियों के लिए O(log n))। उदाहरण हैं: JSON पार्स करना, निर्देशिका का भ्रमण, खेल-वृक्ष और पश्च-अनुसरण की समस्याएँ। इन मामलों में समतुल्य पुनरावृत्तिमूलक संस्करण की तुलना में पुनरावर्ती कोड छोटा, अधिक स्पष्ट और सही सिद्ध करना आसान होता है।
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]जब पुनरावृत्ति स्पष्ट रूप से बेहतर हो
इन स्थितियों में पुनरावृत्ति सही विकल्प है: जब गहराई O(n) हो और n बड़ा हो (सुरक्षित Python कोड में लगभग 500 से अधिक), जब पुनरावर्ती और पुनरावृत्तिमूलक संस्करण समान रूप से पढ़ने योग्य हों (फिबोनाची, क्रमगुणित), या जब समस्या मूलतः क्रमिक हो और उप-समस्याओं में बाँटने का कोई स्वाभाविक तरीका न हो। सरणियों को बाएँ से दाएँ संसाधित करने वाले सरल लूप — संचयी योग, सरकती खिड़कियाँ और दो पॉइंटर — हमेशा पुनरावृत्तिमूलक होने चाहिए।
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceDFS पुनरावर्तन को पुनरावृत्ति में बदलना
एक व्यवस्थित तरीका यह है: हर पुनरावर्ती DFS को पुनरावृत्तिमूलक बनाने के लिए पुनरावर्ती तर्कों को एक स्पष्ट स्टैक पर डालें। मुख्य बात यह है कि पुनरावर्ती आह्वान f(args) के समतुल्य args को स्टैक पर डालकर लूप चलाना है। पश्च-क्रम प्रसंस्करण के लिए (जहाँ मूल नोड से पहले उसकी संततियों के परिणाम चाहिए) आपको दो-चरणीय तरीका या भ्रमण-चिह्न की आवश्यकता हो सकती है।
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]पुनरावर्तन की प्रदर्शन-लागत
Python में हर पुनरावर्ती आह्वान की लागत नगण्य नहीं होती: एक नया फ़्रेम बनाया जाता है (हीप पर स्मृति आवंटित होती है), स्थानीय चरों को आरंभ किया जाता है और वापसी-पते का पॉइंटर संग्रहीत किया जाता है। मानक परीक्षणों से पता चलता है कि Python में फ़ंक्शन आह्वान की अतिरिक्त लागत प्रति आह्वान लगभग 100–200 नैनोसेकंड होती है। 10^6 की पुनरावर्तन गहराई के लिए यह केवल अतिरिक्त लागत 0.1–0.2 सेकंड तक पहुँच जाती है, चाहे कलनविधि का वास्तविक कार्य कुछ भी हो। पुनरावृत्तिमूलक लूप इस लागत से पूरी तरह बचते हैं।
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')साक्षात्कार में निर्णय लेना
कोडिंग साक्षात्कार में, यदि आपके पास विकल्प हो, तो पूछें: 'क्या पुनरावर्तन की गहराई O(log n) से सीमित है?' यदि हाँ, तो पुनरावर्तन ठीक है। 'क्या पुनरावर्तन की गहराई O(n) है?' — पुनरावृत्ति को प्राथमिकता दें या बताएँ कि उत्पादन में इसे पुनरावृत्तिमूलक बना देंगे। 'क्या समस्या स्वाभाविक रूप से वृक्ष-जैसी या विभाजन-और-विजय वाली है?' — पुनरावर्ती तरीके की ओर झुकें। 'क्या समस्या एक क्रमिक स्कैन है?' — पुनरावृत्ति का उपयोग करें।
अपने तर्क को हमेशा स्पष्ट करें: 'मैं यहाँ पुनरावर्तन का उपयोग करूँगा, क्योंकि संतुलित BST के लिए गहराई O(log n) है, इसलिए O(log n) स्टैक स्थान स्वीकार्य है।'
सारांश: लाभ-हानि सारणी
लाभ-हानि का सारांश: पुनरावर्ती कोड अक्सर छोटा होता है और समस्या की संरचना को प्रतिबिंबित करता है, लेकिन इसके लिए O(गहराई) स्टैक स्थान चाहिए और फ़ंक्शन-आह्वान की अतिरिक्त लागत भी होती है। पुनरावृत्तिमूलक कोड लंबा होता है, लेकिन O(1) स्टैक स्थान का उपयोग करता है और पुनरावर्तन की सीमाओं से बचता है। मेमोइज़ेशन वाला पुनरावर्तन (अगले पाठ में) बीच का रास्ता है: पुनरावर्तन की स्पष्टता बनाए रखते हुए अनावश्यक पुनर्गणना समाप्त करता है। अपने समाधान का विश्लेषण करते समय कॉल-स्टैक स्थान सहित स्थान जटिलता को हमेशा स्पष्ट रूप से बताएँ।
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')त्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाओं और एल्गोरिद्म — कोडिंग साक्षात्कार तैयारी — की अवधारणाओं पर अपनी समझ का परीक्षण करें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: जब गहराई O(log n) हो या समस्या स्वाभाविक रूप से वृक्ष-जैसी हो, तब पुनरावर्तन को प्राथमिकता दी जाती है; जब गहराई O(n) हो या समस्या क्रमिक हो, तब पुनरावृत्ति को, सरल पुनरावर्ती फिबोनाची O(2^n) होता है — पुनरावृत्तिमूलक संस्करण का समय O(n) और स्थान O(1) होता है, और हर पुनरावर्ती DFS को हीप पर स्पष्ट स्टैक का प्रबंधन करके पुनरावृत्तिमूलक बनाया जा सकता है। अगले पाठ में हम अनावश्यक पुनरावर्ती आह्वानों को समाप्त करने के लिए मेमोइज़ेशन लागू करेंगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “पुनरावर्ती बनाम पुनरावृत्तीय संतुलन” पाठ निःशुल्क है?
हाँ—“पुनरावर्ती बनाम पुनरावृत्तीय संतुलन” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“पुनरावर्ती बनाम पुनरावृत्तीय संतुलन” में मैं क्या सीखूँगा?
पुनरावर्ती factorial और Fibonacci को पुनरावृत्त लूप में बदलिए तथा समझाइए कि Python की पुनरावृत्ति सीमा और स्टैक आकार कब पुनरावृत्तीय तरीका बेहतर बनाते हैं। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“पुनरावर्ती बनाम पुनरावृत्तीय संतुलन” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण
- कॉल स्टैक का दृश्यांकन
- पुनरावर्ती बनाम पुनरावृत्तीय संतुलन
- Memoisation: पुनरावर्ती परिणामों का कैशिंग