末尾呼び出し最適化 (Tail Call Optimization)

C言語, C++ 2013/10/08

末尾の関数コールの最適化はしてくれない。

Go言語 (golang) 2015/02/24

末尾の関数コールの最適化はしてくれない。

Goで再帰使うと遅くなりますがそれが何だ | YAMAGUCHI::weblog 2015/02/24

http://ymotongpoo.hatenablog.com/entry/2015/02/23/165341

Java 2013/10/08

末尾の関数コールの最適化はしてくれない。

Scala 2014/06/16

末尾再帰のループへの変換などへの最適化ができる場合は、コンパイラが自動でそのようにしてくれる。

末尾再帰以外の末尾関数呼び出しの最適化してくれない。JVMの仕様上、難しい。

@scala.annotation.tailrec アノテーションをメソッドに付けると、そのメソッドの再帰呼び出しの箇所が末尾再帰の最適化にならない場合にコンパイルエラーになってくれるので、末尾再帰の場合はこれを付けたほうがよい。

メソッドがオーバーライド可能だと、末尾再帰の最適化ができないので、 final も付ける必要がある。

フィボナッチ数列を計算する例

import scala.annotation.tailrec;

// 末尾再帰になっていない再帰のフィボナッチ
// @tailrec を付けるとコンパイラに
// error: could not optimize @tailrec annotated method fib: it contains a recursive call not in tail position
// と言われる
def fib(n: Int): Int = {
  if (n <= 2) {
    1;
  } else {
    fib(n - 1) + fib(n - 2);
  }
}

// 末尾再帰のフィボナッチ
def fib_r(n: Int): Int = fib_r_sub(n, 1, 0);

@tailrec
def fib_r_sub(n: Int, a: Int, b: Int): Int = {
  if (n <= 1) {
    a;
  } else if (n == 2) {
    a + b;
  } else {
    fib_r_sub(n - 1, a + b, a);
  }
}

println(fib(8));
// => 21

println(fib_r(8));
// => 21

PHP 2013/10/25

末尾の関数コールの最適化はしてくれない。

Python 2013/10/25

末尾の関数コールの最適化はしてくれない。

Ruby 2015/02/17

標準では末尾の関数コールの最適化はしてくれないが、最近のRubyではオプションで最適化を有効にできる。

フィボナッチ数列を計算する例 (この例では再帰が浅すぎて最適化してなくても実行できてしまうが)

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

RubyVM::InstructionSequence.new(<<-'EOF').eval

  def fib_r(n)
    fib_r_sub(n, 1, 0)
  end

  def fib_r_sub(n, a, b)
    if n <= 1
      a
    elsif n == 2
      a + b
    else
      fib_r_sub(n - 1, a + b, a)
    end
  end

  p fib_r(8)
  # => 21

EOF

3つのメソッドの相互再帰呼び出しの例 (無限再帰なので最適化が必須)

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

RubyVM::InstructionSequence.new(<<-'EOF').eval

  def f(a)
    puts "f: #{a}"
    g(a + 1)
  end

  def g(a)
    puts "g: #{a}"
    h(a + 1)
  end

  def h(a)
    puts "h: #{a}"
    f(a + 1)
  end

  f(0)

EOF

以下のバージョンで試したが全部この方法で実行できた。

1.9.2-p330
1.9.3-p551
2.0.0-p598
2.1.5

JRuby 2015/02/17

末尾の関数コールの最適化はしてくれない。

上記のRubyのサンプルを実行しようとすると、 NameError: uninitialized constant RubyVM というエラーが発生してしまう。

Perl 2014/01/15

末尾の関数コールの最適化はしてくれない。