Ruby Language
Rekursion in Ruby

Rekursive Funktion

Beginnen wir mit einem einfachen Algorithmus, um zu sehen, wie Rekursion in Ruby implementiert werden kann.

Eine Bäckerei hat Produkte zu verkaufen. Produkte sind in Packungen. Bestellungen werden nur in Paketen bearbeitet. Die Verpackung beginnt mit der größten Packungsgröße, und die verbleibenden Mengen werden mit den nächsten verfügbaren Packungsgrößen gefüllt.

ZB wenn eine Bestellung von 16 eingeht, werden in der Bäckerei 2 aus 5 Packungen und 2 aus 3 Packungen vergeben. 2 5 + 2 3 = 16. Mal sehen, wie dies in Rekursion implementiert wird. "zuteilen" ist hier die rekursive Funktion.

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

Ausgabe ist:

Packungskombination ist: [3, 3, 5, 5]

Schwanzrekursion

Viele rekursive Algorithmen können durch Iteration ausgedrückt werden. Zum Beispiel kann die größte gemeinsame Nennerfunktion rekursiv geschrieben werden :

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

oder iterativ:

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

  return x
end

Die beiden Algorithmen sind theoretisch äquivalent, die rekursive Version birgt jedoch einen SystemStackError . Da die rekursive Methode jedoch mit einem Aufruf an sich selbst endet, könnte sie optimiert werden, um einen Stapelüberlauf zu vermeiden. Anders ausgedrückt: Der rekursive Algorithmus kann zu demselben Maschinencode wie der iterative Code führen, wenn der Compiler am Ende der Methode nach dem rekursiven Methodenaufruf sucht. Ruby führt standardmäßig keine Endanrufoptimierung durch, aber Sie können es mit folgendem Befehl aktivieren:

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

Zusätzlich zum Aktivieren der Rückrufoptimierung müssen Sie auch die Befehlsverfolgung deaktivieren. Leider gelten diese Optionen nur bei der Kompilierung, so müssen Sie entweder require die rekursive Methode aus einer anderen Datei oder eval die Methodendefinition:

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

Schließlich muss der letzte Rückruf die Methode und nur die Methode zurückgeben . Das bedeutet, dass Sie die standardmäßige faktorielle Funktion erneut schreiben müssen:

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

Zu etwas wie:

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

Diese Version übergibt die angesammelte Summe über ein zweites (optionales) Argument, das standardmäßig den Wert 1 hat.

Lesen Sie weiter: Call-Call-Optimierung in Ruby und Tailin 'Ruby .