Scala Language
प्रत्यावर्तन

पूंछ पुनरावृत्ति

नियमित पुनरावर्तन का उपयोग करते हुए, प्रत्येक पुनरावर्ती कॉल कॉल स्टैक पर एक और प्रविष्टि को धक्का देती है। जब पुनरावृत्ति पूरी हो जाती है, तो एप्लिकेशन को प्रत्येक प्रविष्टि को वापस नीचे सभी तरह से पॉप करना होता है। यदि बहुत अधिक पुनरावर्ती फ़ंक्शन कॉल हैं तो यह एक विशाल स्टैक के साथ समाप्त हो सकता है।

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

नियमित पुनरावर्तन

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

def fact(i : Int) : Int = {
   if(i <= 1) i
   else i * fact(i-1)
}

println(fact(5))

पैरामीटर के साथ फ़ंक्शन कॉल इस तरह दिखने वाले स्टैक के परिणामस्वरूप होगा:

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

यदि हम इस उदाहरण को @tailrec साथ एनोटेट करने का प्रयास करते हैं, तो हमें निम्न त्रुटि संदेश मिलेगा: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

पूंछ पुनरावृत्ति

पूंछ पुनरावृत्ति में, आप पहले अपनी गणना करते हैं, और फिर आप पुनरावर्ती कॉल को निष्पादित करते हैं, अपने वर्तमान चरण के परिणामों को अगले पुनरावर्ती चरण में पास करते हैं।

def fact_with_tailrec(i : Int) : Long = {
   @tailrec
   def fact_inside(i : Int, sum: Long) : Long = {
      if(i <= 1) sum
      else fact_inside(i-1,sum*i)
   }
   fact_inside(i,1)
}

println(fact_with_tailrec(5))

इसके विपरीत, पूंछ पुनरावर्ती फैक्टरियल के लिए स्टैक ट्रेस निम्नलिखित की तरह दिखता है:

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

प्रत्येक कॉल के लिए डेटा की समान मात्रा को ट्रैक करने की आवश्यकता केवल fact_inside क्योंकि फ़ंक्शन केवल उस मान को वापस कर रहा है जो इसे शीर्ष के माध्यम से मिला है। इसका मतलब यह है कि भले ही fact_with_tail 1000000 कहा जाता है, इसे fact_with_tail 3 रूप में केवल उसी स्थान की आवश्यकता है। यह गैर-पूंछ-पुनरावर्ती कॉल के मामले में नहीं है, और ऐसे बड़े मूल्यों के कारण स्टैक ओवरफ्लो हो सकता है।

Trampoline (scala.util.control.TailCalls) के साथ निराधार पुनरावृत्ति

पुनरावर्ती फ़ंक्शन को कॉल करते समय एक StackOverflowError त्रुटि प्राप्त करना बहुत आम है। स्काला स्टैंडर्ड लाइब्रेरी रीपर्सन की स्थानीय स्थिति को संग्रहीत करने के लिए ढेर वस्तुओं और निरंतरताओं का उपयोग करके स्टैक ओवरफ्लो से बचने के लिए टेलकॉल प्रदान करता है।

TailCalls के स्केलडॉक से दो उदाहरण

import scala.util.control.TailCalls._
    
def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
    
def isOdd(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

// Does this List contain an even number of elements?
isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

// What is the 40th entry of the Fibonacci series?
fib(40).result