एक स्टैक का उपयोग करने के लिए एक रिकर्सिव फ़ंक्शन को कैसे परिवर्तित करें?

Question

मान लीजिए कि मैं एक गहराई पहले खोज का उपयोग पार करने के लिए एक पेड़ है, और इसे traversing के लिए मेरे एल्गोरिथ्म कुछ इस तरह दिखता है: कई भाषाओं में अब

algorithm search(NODE): 
    doSomethingWith(NODE) 
    for each node CHILD connected to NODE: 
    search(CHILD) 

वहाँ उदाहरण है अगर के लिए प्रत्यावर्तन के लिए अधिकतम गहराई है, रिकर्सन की गहराई एक निश्चित सीमा से अधिक है, तो प्रक्रिया एक ढेर ओवरफ्लो के साथ दुर्घटनाग्रस्त हो जाएगी।

इस समारोह को रिकर्सन के बिना कैसे लागू किया जा सकता है, और इसके बजाय एक ढेर के साथ? कई मामलों में, बहुत सारे स्थानीय चर हैं; वे कहाँ से संग्रहीत किया जा सकता है?

Answer 1

आप इसे बदल इसलिए जैसे एक ढेर का उपयोग करें:

algorithm search(NODE): 
    createStack() 
    addNodeToStack(NODE) 

    while(stackHasElements) 
     NODE = popNodeFromStack() 
     doSomethingWith(NODE) 
     for each node CHILD connected to NODE: 
     addNodeToStack(CHILD) 

अपने दूसरे प्रश्न का सवाल है:

कई मामलों में, टी यहां बहुत सारे स्थानीय चर हैं; वे कहाँ से संग्रहीत किया जा सकता है?

इन्हें वास्तव में उसी स्थान पर रखा जा सकता है जैसा वे मूल रूप से थे। यदि चर "doSomethingWith" विधि के लिए स्थानीय हैं, तो बस उन्हें उसमें ले जाएं, और इसे एक अलग विधि में दोबारा दोहराएं। इस विधि को ट्रैवर्सल को संभालने की आवश्यकता नहीं है, केवल प्रसंस्करण, और इसके अपने स्थानीय चर भी इस तरह से हो सकते हैं जो केवल इसके दायरे में काम करता है।

Answer 2

अनिवार्य रूप से आप अपने खुद के ढेर के ऊपर नया: या प्रकार-सुरक्षा के लिए, node* in_process[] = new node*[1024]; और इस पर अपने मध्यवर्ती मूल्यों डाल: एक अलग ट्रेवर्सल लिए

node** current = &in_process[0]; 
node* root = getRoot(); 

recurse(root, &current) ;** 

void recurse(node* root, node** current) ; 
    *(*current)++ = root; add a node 
    for(child in root) { 
    recurse(child, current); 
    } 
    --*current; // decrement pointer, popping stack; 
} 

Answer 3

।

push(root) 
while not empty: 
    node = pop 
    doSomethingWith node 
    for each node CHILD connected to NODE: 
     push(CHILD) 

एक समान ट्रैवर्सल के लिए नोड्स को रिवर्स ऑर्डर में धक्का दें।

आप अपने ढेर बह रहे हैं, तो यह शायद मदद नहीं करेगा, जैसा कि आप अपने ढेर उड़ा देंगे बजाय

यदि आप एक nextChild कार्य हो आप सभी बच्चों को आगे बढ़ाने से बच सकते हैं

Answer 4

एरिक लिपर्ट ने इस विषय के बारे में कई पोस्ट बनाई हैं। उदाहरण के लिए इस पर एक नज़र डालें: Recursion, Part Two: Unrolling a Recursive Function With an Explicit Stack