Ruby Language
Recursie in Ruby

Recursieve functie

Laten we beginnen met een eenvoudig algoritme om te zien hoe recursie in Ruby kan worden geïmplementeerd.

Een bakkerij heeft producten om te verkopen. Producten zitten in pakketten. Het bedient alleen bestellingen in pakketten. De verpakking begint bij de grootste verpakkingsgrootte en vervolgens worden de resterende hoeveelheden gevuld met de volgende beschikbare verpakkingsgroottes.

Voor bijvoorbeeld als een bestelling van 16 wordt ontvangen, wijst de bakkerij 2 uit 5 verpakkingen en 2 uit 3 verpakkingen toe. 2 5 + 2 3 = 16. Laten we eens kijken hoe dit wordt geïmplementeerd in recursie. "toewijzen" is hier de recursieve functie.

#!/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}"

Uitgang is:

Pack-combinatie is: [3, 3, 5, 5]

Staart recursie

Veel recursieve algoritmen kunnen worden uitgedrukt met behulp van iteratie. De grootste gemene delerfunctie kan bijvoorbeeld recursief worden geschreven :

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

of iteratief:

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

  return x
end

De twee algoritmen zijn in theorie equivalent, maar de recursieve versie riskeert een SystemStackError . Omdat de recursieve methode echter eindigt met een aanroep naar zichzelf, kan deze worden geoptimaliseerd om een stack-overflow te voorkomen. Een andere manier om het te zeggen: het recursieve algoritme kan dezelfde machinecode als de iteratieve code opleveren als de compiler weet te zoeken naar de recursieve methodeaanroep aan het einde van de methode. Ruby voert standaard geen staartoproepoptimalisatie uit, maar u kunt het inschakelen met :

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

Naast het inschakelen van tail-call-optimalisatie, moet u ook het traceren van instructies uitschakelen. Helaas zijn deze opties zijn alleen van toepassing tijdens het compileren, dus je ofwel moeten require de recursieve methode vanuit een ander bestand of eval de methode definitie:

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

Ten slotte moet de laatste terugkeeroproep de methode retourneren en alleen de methode . Dat betekent dat u de standaardfactoriële functie opnieuw moet schrijven:

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

Naar iets als:

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

Deze versie geeft de verzamelde som door via een tweede (optioneel) argument dat standaard op 1 staat.

Verder lezen: Tail Call Optimization in Ruby en Tailin 'Ruby .