Ruby Language
Ricorsione in Ruby
Ricerca…
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 .