More than 5 years have passed since last update.

再帰関数を末尾再帰にする方法

Posted at 2019-06-05

再帰関数を書くときにはスタックコールが積まれないように
末尾再帰になっているかどうか注意する必要があります。

Rubyで末尾再帰になってない、
配列の要素数を数えるmy_lengthを実装すると

def my_length(array)
  if array[0].present?
    1 + my_length(array[1..-1])
  else
    0
  end
end

my_length([2,3,4,5])
=> 4

になります。

この場合再帰関数を呼び出す前に1を加算してるため、
スタックコールが積まれてしまいます。

末尾再帰にするためには、アキュムレーターを使い

def my_length(array, accum)
  if array[0].present?
    my_length(array[1..-1], (accum + 1))
  else
    return accum
  end
end

my_length([2,3,4,5], 0)
=> 4

にすることで末尾再帰関数になります。