尾遞迴

可以使用迭代來表達許多遞迴演算法。例如,最大的公分母函式可以遞迴寫入

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
}

除了開啟尾呼叫優化之外,你還需要關閉指令跟蹤。不幸的是,這些選項僅適用於編譯時,因此你需要從另一個檔案中提取遞迴方法或者方法定義:

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 的第二個(可選)引數傳遞累計和。

進一步閱讀: RubyTailin’Ruby 中的 尾調優化