Ruby Language
Ricorsione in Ruby

Funzione ricorsiva

Iniziamo con un semplice algoritmo per vedere come la ricorsione potrebbe essere implementata in Ruby.

Un panificio ha prodotti da vendere. I prodotti sono in confezioni. Serve solo ordini in pacchetti. L'imballaggio inizia dalla confezione più grande e le quantità rimanenti vengono riempite dalle confezioni successive disponibili.

Ad esempio, se viene ricevuto un ordine di 16, la panetteria assegna 2 pacchetti da 5 e 2 pacchetti da 3. 2 5 + 2 3 = 16. Vediamo come questo è implementato in ricorsione. "allocare" è la funzione ricorsiva qui.

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

L'output è:

La combinazione di pacchetti è: [3, 3, 5, 5]

Ricorsione di coda

Molti algoritmi ricorsivi possono essere espressi usando l'iterazione. Ad esempio, la massima funzione denominatore comune può essere scritta in modo ricorsivo :

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

o iterativamente:

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

  return x
end

I due algoritmi sono equivalenti in teoria, ma la versione ricorsiva rischia un SystemStackError . Tuttavia, poiché il metodo ricorsivo termina con una chiamata a se stesso, potrebbe essere ottimizzato per evitare un overflow dello stack. Un altro modo per dirla: l'algoritmo ricorsivo può generare lo stesso codice macchina del iterativo se il compilatore sa cercare la chiamata al metodo ricorsiva alla fine del metodo. Ruby non ottimizza le chiamate tail per impostazione predefinita, ma puoi attivarlo con :

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

Oltre a attivare l'ottimizzazione della coda, è necessario disattivare anche la traccia delle istruzioni. Sfortunatamente, queste opzioni si applicano solo al momento della compilazione, quindi è necessario require il metodo ricorsivo da un altro file o eval la definizione del metodo:

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

Infine, la chiamata di ritorno finale deve restituire il metodo e solo il metodo . Ciò significa che dovrai riscrivere la funzione fattoriale standard:

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

Per qualcosa come:

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

Questa versione passa la somma accumulata tramite un secondo argomento (facoltativo) che assume come valore predefinito 1.

Ulteriori letture: Ottimizzazione chiamata coda in Ruby e Tailin 'Ruby .