Ruby Language
Rekurencja w Ruby

Funkcja rekurencyjna

Zacznijmy od prostego algorytmu, aby zobaczyć, jak można zaimplementować rekurencję w Ruby.

Piekarnia ma produkty do sprzedania. Produkty są w paczkach. Obsługuje tylko zamówienia w paczkach. Opakowanie zaczyna się od największego rozmiaru opakowania, a następnie pozostałe ilości są wypełniane przez kolejne dostępne rozmiary opakowań.

Na przykład w przypadku otrzymania zamówienia na 16, piekarnia przydziela 2 z 5 opakowań i 2 z 3 opakowań. 2 5 + 2 3 = 16. Zobaczmy, jak jest to realizowane w rekurencji. „przydział” jest tutaj funkcją rekurencyjną.

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

Dane wyjściowe to:

Kombinacja pakietów to: [3, 3, 5, 5]

Rekurencja ogona

Wiele algorytmów rekurencyjnych można wyrazić za pomocą iteracji. Na przykład największą wspólną funkcję mianownika można zapisać rekurencyjnie :

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

lub iteracyjnie:

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

  return x
end

Te dwa algorytmy są teoretycznie równoważne, ale wersja rekurencyjna ryzykuje błąd SystemStackError . Ponieważ jednak metoda rekurencyjna kończy się wywołaniem do siebie, można ją zoptymalizować, aby uniknąć przepełnienia stosu. Innymi słowy: algorytm rekurencyjny może dać ten sam kod maszynowy co iteracyjny, jeśli kompilator wie, że szuka wywołania metody rekurencyjnej na końcu metody. Ruby domyślnie nie wykonuje optymalizacji ogonów, ale możesz ją włączyć za pomocą :

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

Oprócz włączenia optymalizacji połączeń z ogonem musisz także wyłączyć śledzenie instrukcji. Niestety, te opcje obowiązują tylko w czasie kompilacji, więc musisz albo require metody rekurencyjnej z innego pliku, albo eval definicję metody:

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

Wreszcie ostatnie wywołanie zwrotne musi zwrócić metodę i tylko metodę . Oznacza to, że musisz ponownie napisać standardową funkcję silni:

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

Do czegoś takiego:

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

Ta wersja przekazuje zakumulowaną sumę za pomocą drugiego (opcjonalnego) argumentu, który domyślnie wynosi 1.

Dalsza lektura: Optymalizacja wywołania ogona w Ruby i Tailin 'Ruby .