रूबी रिकर्सन और मेमोइज़ेशन में महारत: एक व्यावहारिक गाइड

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

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

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

रूबी रिकर्सन

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

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

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

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

उदाहरण:

 def iterative_factorial(n)
  (1..n).inject(:*)
end
def recursive_factorial(n)
  # बेस केस
  return 1 if n <= 1
  # रिकर्सिव कॉल
  n * recursive_factorial(n-1)
end 

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

रिकर्सिव समाधान में हम उस संख्या को घटाकर प्रगति करते हैं जिस पर हम काम कर रहे हैं (n-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) } 

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

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

छवि में हम देख सकते हैं कि fib(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

निष्कर्ष

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

अगर आपको यह पसंद आया तो इस पोस्ट को शेयर करें और मेरे न्यूज़लेटर की सदस्यता लें 🙂