अनंत रिकर्सन ने एफ # में एक स्टैक ओवरफ़्लो अपवाद क्यों नहीं मारा?

Question

मुझे पता है कि यह कुछ हद तक समस्या का विपरीत है जब लोग एक स्टैक ओवरफ़्लो समस्या के बारे में पूछते हैं, लेकिन यदि मैं कोई फ़ंक्शन बनाता हूं और इसे निम्नानुसार कॉल करता हूं, तो मुझे कभी भी कोई त्रुटि नहीं मिलती है, और एप्लिकेशन बस कोर को पीसता है मेरे CPU के मैं जब तक यह बलपूर्वक-बाहर निकलने:

let rec recursionTest (x: uint64) = 
    recursionTest (x + 1UL) 

recursionTest 0UL 

इस तरह से मैं कभी कभी मेरे कोड में एक ब्रेकपाइंट रख सकते हैं:

let rec recursionTest x = 
    recursionTest x 

recursionTest 1 

बेशक

मैं तो यह वास्तव में कुछ इस तरह करता है यह पता बदल सकते हैं और देखें कि एक्स का मान तेजी से बढ़ रहा है, लेकिन यह अभी भी शिकायत नहीं करता है। एफ # असीमित रिकर्सन नहीं है?

Answer 1

आपका recursionTest समारोह पूंछ पुनरावर्ती है, जो सभी पुनरावर्ती कॉल का अर्थ है 'पूंछ स्थिति' अर्थात समारोह में अंतिम क्रिया के रूप में में होता है। इसका मतलब है कि एफ # कंपाइलर को रिकर्सिव कॉल के लिए एक नया स्टैक फ्रेम आवंटित करने की आवश्यकता नहीं है, इसलिए कोई स्टैक ओवरफ़्लो नहीं होता है।

पूंछ रिकर्सन tail call का एक विशिष्ट मामला है, पूंछ कॉल किसी अन्य कार्य के बजाय स्वयं के लिए है।

Answer 2

यह tail call optimization का एक उदाहरण है और इसलिए संकलक इसे सरल लूप में अनुकूलित कर रहा है। देखें: http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx

कुछ इस तरह का प्रयास करें:

let rec recursionTest x = 
    recursionTest x + recursionTest (x * 2) 

Answer 3

सामान्य में, एफ # tailcall अनुदेश कि सम्मान नेट का उत्सर्जन करता है:

http://msdn.microsoft.com/en-us/library/system.reflection.emit.opcodes.tailcall(v=vs.95).aspx

कुछ विशिष्ट सामान्य मामलों में, आपके जैसे, एफ # प्रोग्राम हैं जो छोरों का उपयोग कर बराबर कार्यक्रमों में प्रत्यावर्तन का उपयोग पुनर्लेखन।