Ruby Language
रूबी में रिक्रिएशन

पुनरावर्ती कार्य

आइए एक सरल एल्गोरिथ्म से शुरू करते हैं, यह देखने के लिए कि रूबी में रिकर्सन कैसे लागू किया जा सकता है।

एक बेकरी में बेचने के लिए उत्पाद हैं। उत्पाद पैक में हैं। यह पैक में ही ऑर्डर देता है। पैकेजिंग सबसे बड़े पैक आकार से शुरू होती है और फिर शेष मात्रा अगले पैक आकारों में उपलब्ध होती है।

उदाहरण के लिए, यदि 16 का आदेश प्राप्त होता है, तो बेकरी 5 से 2 पैक और 3 पैक से 2 आवंटित करता है। 2 5 + 2 3 = 16. आइए देखें कि यह कैसे पुनरावृत्ति में लागू किया जाता है। "आवंटित" यहाँ पुनरावर्ती कार्य है।

#!/usr/bin/ruby

class Bakery
  attr_accessor :selected_packs

  def initialize
    @packs = [5,3] # pack sizes 5 and 3
    @selected_packs = []
  end

  def allocate(qty)
    remaining_qty = nil

    # ==============================================
    # packs are allocated in large packs first order
    # to minimize the packaging space
    # ==============================================
    @packs.each do |pack|
      remaining_qty = qty - pack

      if remaining_qty > 0
        ret_val = allocate(remaining_qty)
        if ret_val == 0
          @selected_packs << pack
          remaining_qty = 0
          break
        end
      elsif remaining_qty == 0
        @selected_packs << pack
        break
      end
    end

    remaining_qty
  end
end

bakery = Bakery.new
bakery.allocate(16)
puts "Pack combination is: #{bakery.selected_packs.inspect}"

आउटपुट है:

पैक संयोजन है: [३, ३, ५, ५]

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

पुनरावृत्ति का उपयोग करके कई पुनरावर्ती एल्गोरिदम व्यक्त किए जा सकते हैं। उदाहरण के लिए, सबसे बड़ा सामान्य भाजक फ़ंक्शन को पुनरावर्ती लिखा जा सकता है :

def gdc (x, y)
  return x if y == 0
  return gdc(y, x%y)
end

या पुनरावृति:

def gdc_iter (x, y)
  while y != 0 do
    x, y = y, x%y
  end

  return x
end

दो एल्गोरिदम सिद्धांत में बराबर हैं, लेकिन पुनरावर्ती संस्करण एक SystemStackError को जोखिम में डालते हैं । हालाँकि, चूंकि पुनरावर्ती पद्धति स्वयं कॉल के साथ समाप्त होती है, इसलिए इसे स्टैक ओवरफ़्लो से बचने के लिए अनुकूलित किया जा सकता है। इसे लगाने का एक और तरीका: पुनरावर्ती एल्गोरिथ्म में पुनरावृत्ति के समान मशीन कोड हो सकता है यदि कंपाइलर विधि के अंत में पुनरावर्ती विधि कॉल की तलाश करना जानता है। रूबी डिफ़ॉल्ट रूप से पूंछ कॉल अनुकूलन नहीं करता है, लेकिन आप इसे चालू कर सकते हैं :

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

टेल-कॉल ऑप्टिमाइज़ेशन को चालू करने के अलावा, आपको इंस्ट्रक्शन ट्रेसिंग को भी बंद करना होगा। दुर्भाग्य से, इन विकल्पों में केवल संकलन समय पर लागू होते हैं, तो आप या तो जरूरत require किसी अन्य फ़ाइल से पुनरावर्ती विधि या eval विधि परिभाषा:

RubyVM::InstructionSequence.new(<<-EOF).eval
  def me_myself_and_i
    me_myself_and_i
  end
EOF
me_myself_and_i # Infinite loop, not stack overflow

अंत में, अंतिम रिटर्न कॉल को विधि और केवल विधि वापस करनी चाहिए। इसका मतलब है कि आपको मानक फैक्टरियल फ़ंक्शन को फिर से लिखना होगा:

def fact(x)
  return 1 if x <= 1
  return x*fact(x-1)
end

कुछ इस तरह से:

 def fact(x, acc=1)
   return acc if x <= 1
   return fact(x-1, x*acc)
 end

यह संस्करण एक दूसरे (वैकल्पिक) तर्क के माध्यम से संचित राशि को पारित करता है जो 1 को चूकता है।

आगे पढ़ने: रूबी और टेलिन रूबी में टेल कॉल ऑप्टिमाइज़ेशन ।