स्कैला नौसिखिया: रिकर्सन और स्टैक ओवरफ्लो त्रुटि

Question

स्कैला नौसिखिया के रूप में, मैं किताबें, दस्तावेज़ पढ़ रहा हूं और http://aperiodic.net/phil/scala/s-99/ पर मिली समस्याओं को हल करने का प्रयास करता हूं। ऐसा लगता है कि सही स्कैला कोड समानांतरता को सुरक्षित बनाने और ताले का उपयोग करने से बचने के लिए लूप और चर के बजाए अपरिवर्तनीय मूल्यों (वैल्यू) और रिकर्सन पर आधारित है।

उदाहरण के लिए, व्यायाम P22 के लिए एक संभव समाधान (http://aperiodic.net/phil/scala/s-99/p22.scala) है:

// Recursive. 
def rangeRecursive(start: Int, end: Int): List[Int] = 
if (end < start) Nil 
else start :: rangeRecursive(start + 1, end) 

बेशक इस कोड को कॉम्पैक्ट है और स्मार्ट लग रहा है लेकिन निश्चित रूप से, अगर प्रत्यावर्तन की संख्या अधिक है, आप करेंगे एक स्टैक ओवरफ्लो त्रुटि का सामना करें (रेंजक्रुसेसरिव (1,10000) उदाहरण के लिए कोई जेवीएम ट्यूनिंग नहीं है)। यदि आप अंतर्निहित List.range (https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1) के स्रोत को देखते हैं, तो आप देखेंगे कि लूप और वर्रों का उपयोग किया जाता है।

मेरा सवाल है कि स्केल सीखने वाली सामग्री के प्रभाव को कैसे प्रबंधित किया जाए जो vals और recursion को बढ़ावा दे रहा है यह जानकर कि इस तरह का कोड रिकर्सन की संख्या के कारण टूट सकता है?

Answer 1

स्कैला के बारे में अच्छी बात यह है कि आप इसमें अपना रास्ता आसान बना सकते हैं। शुरू करना, आप लूप लिख सकते हैं, और भाषा के साथ अधिक आरामदायक होने के साथ रिकर्सन के साथ और अधिक कर सकते हैं। आप क्लोजर या हास्केल जैसी अधिक 'शुद्ध' कार्यात्मक भाषाओं के साथ ऐसा नहीं कर सकते हैं। दूसरे शब्दों में, आप अपरिवर्तनीयता और val के साथ सहज महसूस कर सकते हैं, और बाद में रिकर्सन पर जा सकते हैं।

जब आप रिकर्सन के साथ शुरू करते हैं, तो आपको पूंछ कॉल रिकर्सन देखना चाहिए। यदि रिकर्सिव कॉल फ़ंक्शन में अंतिम कॉल है, तो स्कैला कंपाइलर इसे बाइटकोड में लूप में अनुकूलित करेगा। इस तरह, आपको StackOverflowError एस नहीं मिलेगा। साथ ही, यदि आप अपने रिकर्सिव फ़ंक्शन में @tailrec एनोटेशन जोड़ते हैं, तो संकलक आपको चेतावनी देगा कि आपका फ़ंक्शन पूंछ कॉल रिकर्सिव नहीं है।

उदाहरण के लिए, आपके प्रश्न में फ़ंक्शन पूंछ कॉल रिकर्सिव नहीं है। ऐसा लगता है कि rangeRecursive पर कॉल फ़ंक्शन में आखिरी है, लेकिन जब यह कॉल लौटाता है, तो उसे अभी भी कॉल के परिणामस्वरूप start जोड़ना होगा। इसलिए, यह पूंछ कॉल रिकर्सिव नहीं हो सकता है: कॉल रिटर्न होने पर इसे अभी भी काम करना होगा।

Answer 2

यदि आप उपरोक्त को फिर से लिखते हैं तो यह पूंछ रिकर्सिव है, संकलक कोड को थोड़ी देर में अनुकूलित करेगा। Addititonally आप @tailrec एनोटेशन का उपयोग त्रुटि प्राप्त करने के लिए कर सकते हैं जब यह एनोटेटिंग विधि पूंछ रिकर्सिव नहीं है। इस प्रकार आपको यह जानने में सक्षम बनाता है कि "जब आपको यह सही लगेगा"।

Answer 3

यहां विधि विधि रिकर्सिव बनाने का एक उदाहरण दिया गया है। @tailrec एनोटेशन आवश्यक नहीं है, संकलक इसके बिना अनुकूलित करेगा। लेकिन यह संकलक को एक त्रुटि को ध्वजांकित करता है जब यह अनुकूलन नहीं कर सकता है।

scala> def rangeRecursive(start: Int, end: Int): List[Int] = { 
    | @scala.annotation.tailrec 
    | def inner(accum : List[Int], start : Int) : List[Int] = { 
    |  if (end < start) accum.reverse 
    |  else inner(start :: accum, start + 1) 
    | } 
    | 
    | inner(Nil, start) 
    | } 
rangeRecursive: (start: Int,end: Int)List[Int] 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

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

Answer 4

यहाँ, जेम्स Iry के जवाब के लिए एक विकल्प है ही व्यवहार के साथ:

def rangeRecursive(start: Int, end: Int): List[Int] = { 
    def inner(start : Int) : Stream[Int] = { 
     if (end < start) Stream.empty 
     else start #:: inner(start + 1) 
    } 

    inner(start).toList 
} 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

यह फेंक नहीं है एक StackOverflowError क्योंकि Stream.cons -operator (#::) संदर्भ द्वारा पूंछ संग्रहीत करता है।दूसरे शब्दों में, स्ट्रीम तत्वों की गणना stream.toList तक नहीं की जाती है।

मेरी राय में, इस (बस Stream.empty द्वारा #:: और Nil द्वारा :: की जगह), क्योंकि यह सबसे निकट अनुभवहीन प्रारंभिक एल्गोरिथ्म जैसा दिखता है संचायक पैटर्न की तुलना में अधिक पठनीय है। इसके अलावा, accum.reverse की कोई आवश्यकता नहीं है, जिसे आसानी से भुलाया जा सकता है।