Ruby Language
Rubyでの再帰

再帰関数

簡単なアルゴリズムから始めて、Rubyでどのように再帰を実装できるかを見てみましょう。

ベーカリーには販売する製品があります。製品はパックに入っています。それはパックのみで注文を処理します。梱包は最大の梱包サイズから開始し、残りの梱包は次の梱包サイズで梱包されます。

たとえば、16の注文が受け取られた場合、ベーカリーは5パックから2を、3パックから2を割り当てます。 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}"

出力は次のとおりです。

パックの組み合わせは：[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

2つのアルゴリズムは理論的には同等ですが、再帰バージョンではSystemStackErrorが発生します。しかし、再帰的メソッドはそれ自身の呼び出しで終了するので、スタックオーバーフローを避けるために最適化することができます。再帰アルゴリズムは、コンパイラがメソッドの終わりに再帰的なメソッド呼び出しを探すことを知っていれば 、繰り返しと同じマシンコードになる可能性があります。 Rubyはデフォルトでテールコールの最適化を行いませんが、あなたはそれを有効にすることができます：

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

テールコール最適化をオンにすることに加えて、命令トレースをオフにする必要もあります。残念ながら、これらのオプションはコンパイル時にのみ適用されるため、別のファイルから再帰メソッドをrequireするか、メソッド定義をevalする必要がrequireます。

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

このバージョンは、累積された合計を2番目の（オプションの）引数で渡します。 デフォルトは1です。

さらに読む： RubyとTailin 'Rubyの テールコール最適化 。