स्मृति उपयोग के संबंध में पुनरावृत्ति बनाम पुनरावृत्ति

Question

मान लीजिए कि मेरे पास कुछ समस्या के लिए एक पुनरावर्ती और एक पुनरावृत्ति समाधान (एक स्टैक का उपयोग करके) है। एक बाइनरी पेड़ के preorder traversal। मौजूदा कंप्यूटरों के साथ, मेमोरी-वार, क्या पुनरावर्तक समाधान पर पुनरावर्ती समाधान का उपयोग करने के लिए कोई फायदा है या इसके विपरीत बहुत बड़े पेड़ों के लिए इसके विपरीत है?

मुझे पता है कि कुछ रिकर्सिव समाधानों के लिए जहां उप-समस्याएं दोहराती हैं, रिकर्सन का उपयोग होने पर अतिरिक्त समय और मेमोरी लागत होती है। मान लें कि यह मामला यहां नहीं है। उदाहरण के लिए,

preOrder(Node n){ 
    if (n == null) return; 
    print(n); 
    preOrder(n.left); 
    preOrder(n.right); 
} 

बनाम

preOrder(Node n){ 
    stack s; 
    s.push(n); 
    while(!s.empty()){ 
     Node node = s.pop(); 
     print(node); 
     s.push(node.right); 
     s.push(node.left); 
    } 
} 

Answer 1

अगर वहाँ ढेर अतिप्रवाह का खतरा (इस मामले में, क्योंकि पेड़ भी अर्द्ध संतुलित होने की गारंटी नहीं कर रहे हैं) है, तो एक मजबूत कार्यक्रम होगा रिकर्सन से बचें और एक स्पष्ट ढेर का उपयोग करें।

स्पष्ट ढेर कम स्मृति का उपयोग कर सकता है, क्योंकि स्टैक फ्रेम रिकर्सिव कॉल के संदर्भ को बनाए रखने के लिए कड़ाई से जरूरी है। (उदाहरण के लिए, स्टैक फ्रेम में कम से कम एक रिटर्न पता और स्थानीय चर शामिल होंगे।)

हालांकि, यदि रिकर्सन गहराई सीमित होने के लिए जाना जाता है, तो गतिशील रूप से आवंटित करने के लिए स्थान और समय बचा सकता है, साथ ही प्रोग्रामर समय। उदाहरण के लिए, संतुलित बाइनरी पेड़ को चलने के लिए केवल पेड़ की गहराई के लिए रिकर्सन की आवश्यकता होती है, जो नोड्स की संख्या लॉग है; यह एक बहुत बड़ी संख्या नहीं हो सकता है।

जैसा कि एक टिप्पणीकार द्वारा सुझाया गया है, एक संभावित परिदृश्य यह है कि पेड़ को सही-सही माना जाता है। उस स्थिति में, आप स्टैक ओवरफ़्लो के बारे में चिंता किए बिना बाएं शाखाओं की मरम्मत कर सकते हैं (जब तक आप पूरी तरह से निश्चित हैं कि पेड़ सही है)। के बाद से दूसरा पुनरावर्ती कॉल पूंछ स्थिति में है, यह सिर्फ एक पाश के रूप में लिखा जा सकता है:

void preOrder(Node n) { 
    for (; n; n = n.right) { 
     print(n); 
     preOrder(n.left); 
     n = n.right; 
} 

ऐसा ही एक तकनीक अक्सर है (और हमेशा होना चाहिए) quicksort के लिए लागू: विभाजन के बाद, समारोह recurses छोटे विभाजन पर, और फिर बड़े विभाजन को संभालने के लिए loops। चूंकि छोटा विभाजन मूल सरणी के आधे आकार से कम होना चाहिए, जो मूल सरणी आकार के लॉग से कम होने के लिए रिकर्सन गहराई की गारंटी देगा, जो निश्चित रूप से 50 से अधिक स्टैक फ्रेम से कम है, और शायद बहुत कम ।