रूबी में रिकर्सन और मेमोइज़ेशन का उपयोग कैसे करें?

रूबी में रिकर्सन क्या है?

पुनरावर्ती कार्य वे हैं जो अंतिम लक्ष्य तक पहुंचने तक स्वयं को कॉल करते रहते हैं (जिसे बेस केस भी कहा जाता है) ) प्रत्येक फ़ंक्शन कॉल के बाद आप इस बेस केस की दिशा में प्रगति करते हैं, जिससे किए जाने वाले काम की मात्रा कम हो जाती है।

एक बार बेस केस तक पहुंचने के बाद, रिकर्सन समाप्त हो जाता है, और फ़ंक्शन वापस आना शुरू हो जाते हैं।

रूबी रिकर्सन

रिकर्सन के बारे में सीखना शुरू करने का एक उत्कृष्ट उदाहरण एक फैक्टोरियल नंबर की गणना करना है।

आइए देखें कि हम इसे रूबी में पुनरावृत्ति और पुनरावृत्ति दोनों का उपयोग करके कैसे कर सकते हैं!

किसी संख्या का भाज्य ज्ञात करने के लिए हमें सभी संख्याओं को 1 से अपनी लक्ष्य संख्या से गुणा करना होता है। उदाहरण के लिए, 5 का भाज्य है:1 * 2 * 3 * 4 * 5 = 120 ।

आइए देखें कि रूबी और रिकर्सन का उपयोग करके हम इसे कैसे कर सकते हैं।

उदाहरण :

def iterative_factorial(n)
  (1..n).inject(:*)
end

def recursive_factorial(n)
  # Base case
  return 1 if n <= 1

  # Recursive call
  n * recursive_factorial(n-1)
end

इस उदाहरण में मैं आपको भाज्य संख्या की गणना करने के दो तरीके दिखाता हूँ। पुनरावृत्त और पुनरावर्ती समाधान।

पुनरावर्ती समाधान में हम उस संख्या को कम करके प्रगति करते हैं जिसके साथ हम काम कर रहे हैं (एन -1)। एक बार (n <=1) कोई और पुनरावर्ती कॉल नहीं हैं, और यही होता है:

return 1      # recursive_factorial(1)
return 2 * 1  # recursive_factorial(2)
return 3 * 2  # recursive_factorial(3)
return 4 * 6  # recursive_factorial(4)
return 5 * 24 # recursive_factorial(5)

रूबी डेवलपर्स के रूप में हम ज्यादातर समय पुनरावृत्त समाधान के लिए जाते हैं, और यह बहुत अच्छा है, लेकिन मुझे लगता है कि यह अभी भी जानने योग्य है कि रिकर्सन कैसे काम करता है।

आइए अब एक और क्लासिक उदाहरण देखें:फाइबोनैचि संख्याएं।

फिबोनाची अनुक्रम

लियोनार्डो फिबोनाची ने इस क्रम की खोज तब की जब यह जांच की गई कि आदर्श परिस्थितियों में खरगोश की आबादी के विकास को कैसे मॉडल किया जाए।

अनुक्रम की गणना वर्तमान संख्या से पहले आने वाली दो संख्याओं को जोड़कर की जाती है।

उदाहरण :

1, 1, 2, 3, 5, 8, 13, 21

रूबी में इसकी गणना करने के लिए आप एक पुनरावर्ती फ़ंक्शन का उपयोग कर सकते हैं:

def fib(n)
  return n if n < 2

  fib(n-1) + fib(n-2)
end

इस फ़ंक्शन और एक श्रेणी का उपयोग करके आप आसानी से पहले 20 फिबोनाची संख्याओं की गणना कर सकते हैं।

(1..20).each { |n| puts fib(n) }

हालांकि, एक समस्या है :

आपका कार्य बहुत अधिक अतिरिक्त कार्य कर रहा है जिसकी उसे आवश्यकता नहीं है। इसे स्पष्ट करने के लिए, निम्न चित्र को देखें।

छवि में हम देख सकते हैं कि कैसे फाइब(3) पांच बार गणना की जाती है। यदि आप लंबे फाइबोनैचि अनुक्रमों की गणना करने का प्रयास करते हैं तो यह आपके कार्य को वास्तव में धीमा कर देता है।

समाधान? संस्मरण।

संस्मरण:हम पहले ही किए गए कार्य का पुन:उपयोग करते हैं

क्या यह बहुत अच्छा नहीं होगा यदि आप पिछले चरणों में पहले से किए गए कार्य का पुन:उपयोग कर सकें?

हम संस्मरण . का उपयोग करके ऐसा कर सकते हैं ।

अपने महंगे गणना परिणामों को बचाने के लिए हम कैश का उपयोग करते हैं। इस मामले में, एक सरणी काम करेगी।

उदाहरण :

@cache = [0,1]

def fib(n)
  return @cache[n] if @cache[n]

  @cache[n] = fib(n-1) + fib(n-2)
end

पहले हम यह देखने के लिए जांचते हैं कि क्या परिणाम पहले से ही कैश में है, यदि यह है तो इसे वापस कर दें, अन्यथा हम गणना करते हैं और परिणाम को सहेजते हैं।

यह बहुत तेजी से चलेगा और यह बहुत बड़ी फाइबोनैचि संख्याओं की गणना करने में सक्षम होगा।

पुनरावृत्ति की सीमाएं

जैसा कि एक पाठक ने कृपया बताया, पुनरावर्ती समाधान SystemStackError: stack level too deep के साथ विफल हो सकता है बड़े इनपुट नंबरों के साथ (लगभग 7500, सटीक संख्या आपके सिस्टम पर निर्भर करती है)।

यदि आपको और भी बड़ी संख्या की गणना करने की आवश्यकता है तो आपको एक पुनरावृत्त समाधान का उपयोग करना होगा।

उदाहरण :

memo = []

(0..n).each do |i|
  memo[i] = i < 2 ? i : memo[i-1] + memo[i-2]
end

निष्कर्ष

रिकर्सन बहुत अच्छा है लेकिन कभी-कभी इसे समझना मुश्किल हो सकता है। अब आपकी बारी है, अभ्यास से महारत हासिल होती है!

कृपया इस पोस्ट को साझा करें यदि आप इसे पसंद करते हैं और मेरे न्यूज़लेटर की सदस्यता लें 🙂