Ruby Language
Рекурсия в Ruby

Рекурсивная функция

Начнем с простого алгоритма, чтобы увидеть, как рекурсия может быть реализована в Ruby.

В пекарне есть продукты для продажи. Продукты находятся в упаковках. Он обслуживает заказы только в пакетах. Упаковка начинается с самого большого размера упаковки, а остальные количества заполняются следующими размерами пакетов.

Например, если получен заказ из 16, пекарня выделяет 2 из 5 пакетов и 2 из 3 пакетов. 2 5 + 2 3 = 16. Посмотрим, как это реализовано в рекурсии. «allocate» - это рекурсивная функция здесь.

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

Выход:

Pack комбинация: [3, 3, 5, 5]

Рекурсия хвоста

Многие рекурсивные алгоритмы могут быть выражены с помощью итерации. Например, наибольшую общую функцию знаменателя можно записать рекурсивно :

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

или итеративно:

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

  return x
end

Оба алгоритма эквивалентны теоретически, но рекурсивная версия подвержена риску SystemStackError . Однако, поскольку рекурсивный метод заканчивается вызовом для себя, его можно оптимизировать, чтобы избежать переполнения стека. Еще один способ: рекурсивный алгоритм может привести к тому же машинного кода, что и итеративный, если компилятор знает, как искать вызов рекурсивного метода в конце метода. По умолчанию Ruby не оптимизирует оптимизацию вызовов, но вы можете включить его с помощью :

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

В дополнение к оптимизации оптимизации хвоста вам также необходимо отключить отслеживание команд. К сожалению, эти параметры применимы только во время компиляции, поэтому вам нужно либо require рекурсивный метод из другого файла, либо eval определение метода:

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

Наконец, окончательный вызов возврата должен возвращать метод и только метод . Это означает, что вам нужно будет переписать стандартную факториальную функцию:

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

К чему-то вроде:

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

Эта версия передает накопленную сумму через второй (необязательный) аргумент, который по умолчанию равен 1.

Дальнейшее чтение: Оптимизация звонков в Ruby и Tailin 'Ruby .