रिकर्सन

Question

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

एक सामान्य समाधान के लिए कोई अन्य सुझाव जो स्पष्ट रूप से रिकर्सिव फ़ंक्शन कैसे लेते हैं और इसे स्टैक पर स्थान बर्बाद किए बिना फिर से लिखते हैं?

बहुत धन्यवाद, पुरानी MCST

Answer 1

अपने कोड पूंछ प्रत्यावर्तन (अर्थात, समारोह हर पुनरावर्ती कॉल का परिणाम देता है सीधे किसी अन्य प्रसंस्करण के बिना) तो यह एक ढेर के बिना लाजि़मी समारोह के पुनर्लेखन के लिए संभव है का उपयोग करता है:

function dosomething(a,b,c,d) 
{ 
    // manipulate a,b,c,d 
    if (condition) 
    return dosomething(a,b,c,d) 
    else 
    return something; 
} 

में:

function dosomething(a,b,c,d) 
{ 
    while (true) 
    { 
    // manipulate a,b,c,d 
    if (condition) continue; 
    else return something; 
    } 
} 

पूंछ प्रत्यावर्तन के बिना, एक ढेर (या किसी ऐसे ही मध्यस्थ भंडारण) का उपयोग केवल समाधान है।

function fib(n) 
{ 
    // valid for n >= 0 
    if (n < 2) 
     return n; 
    else 
     return fib(n-1) + fib(n-2); 
} 

लेकिन Memoization के बिना इस लेता हे (समा^एन) ओ के साथ संचालन (एन) ढेर अंतरिक्ष:

Answer 2

अधिकांश पुनरावर्ती कार्यों को आसानी से अंतरिक्ष बर्बाद कर के रूप में, छोरों के रूप में लिखा जा सकता है - कि समारोह पर निर्भर करता है, के बाद से कई (लेकिन सभी नहीं) पुनरावर्ती एल्गोरिदम वास्तव में उस तरह का पर निर्भर भंडारण (हालांकि, इन मामलों में लूप संस्करण आमतौर पर अधिक कुशल होता है)।

Answer 3

क्लासिक पुनरावर्ती समारोह है कि एक पाश के रूप में लिखा जा सकता है फाइबोनैचि कार्य है।

यह फिर से लिखा जा सकता है:

function fib(n) 
{ 
    if (n < 2) 
     return n; 
    var a = 0, b = 1; 
    while (n > 1) 
    { 
     var tmp = a; 
     a = b; 
     b = b + tmp; 
     n = n - 1; 
    } 
    return b; 
} 

लेकिन यह कैसे समारोह काम करता है, यकीन नहीं अगर यह एक स्वत: प्रक्रिया के लिए सामान्यीकृत किया जा सकता का ज्ञान शामिल है।