Ruby Language
Recursion en Ruby

Función recursiva

Comencemos con un algoritmo simple para ver cómo se podría implementar la recursión en Ruby.

Una panadería tiene productos para vender. Los productos están en paquetes. Atiende pedidos en paquetes únicamente. El empaque comienza desde el tamaño de paquete más grande y luego las cantidades restantes se llenan con los siguientes tamaños de paquete disponibles.

Por ejemplo, si se recibe un pedido de 16, la panadería asigna 2 de 5 paquetes y 2 de 3 paquetes. 2 5 + 2 3 = 16. Veamos cómo se implementa esto en la recursión. "asignar" es la función recursiva aquí.

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

La salida es:

La combinación de paquetes es: [3, 3, 5, 5]

Recursion de cola

Muchos algoritmos recursivos pueden expresarse usando iteración. Por ejemplo, la función de denominador común más grande se puede escribir recursivamente :

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

Los dos algoritmos son equivalentes en teoría, pero la versión recursiva corre el riesgo de un SystemStackError . Sin embargo, dado que el método recursivo termina con una llamada a sí mismo, podría optimizarse para evitar un desbordamiento de pila. Otra forma de decirlo: el algoritmo recursivo puede resultar en el mismo código de máquina que el iterativo si el compilador sabe que debe buscar la llamada al método recursivo al final del método. Ruby no realiza la optimización de llamadas de cola de forma predeterminada, pero puede activarlo con :

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

Además de activar la optimización de llamada de cola, también debe desactivar el seguimiento de instrucciones. Desafortunadamente, estas opciones solo se aplican en el momento de la compilación, por lo que debe require el método recursivo de otro archivo o eval la definición del método:

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

Finalmente, la última llamada devuelta debe devolver el método y solo el método . Eso significa que tendrás que volver a escribir la función factorial estándar:

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

A algo como:

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

Esta versión pasa la suma acumulada a través de un segundo argumento (opcional) que por defecto es 1.

Lectura adicional: Optimización de llamadas de cola en Ruby y Tailin 'Ruby .