Scalaは末尾再帰の最適化をサポートしていますか？

Question

Scalaは末尾再帰の最適化をサポートしていますか？

Answer 1

他のポスターが言っているように、Scalaはコンパイル時にテール再帰の最適化を行います。つまり、テール再帰関数を実行しているときにスタックトレースからわかるように、テール再帰関数はコンパイラによってループに変換されます（メソッド呼び出しはジャンプに変換されます）。

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1) 
boom(10) 

をし、スタックトレースを調べる：

は、次のスニペットを試してみてください。関数boomへの呼び出しは1つしか表示されないため、コンパイルされたバイトコードは再帰的ではありません。

implement tail calls at the JVM levelに浮かぶ提案があります。私の意見では、JVMはコードのコンパイル時の最適化ではなく実行時の最適化を行うことができます。再帰。基本的にはtailcall invokeは通常のメソッドinvokeとまったく同じように動作しますが、安全なときに呼び出し側のスタックを削除します。JITの仕様では、スタックフレームを保存する必要があるため、静的コード分析を行う必要があります。スタックフレームが決して使用されないかどうかを調べる。

現在のステータスはproto 80%です。私はそれがJava 7（invokedynamicがより優先順位が高く、実装がほぼ完了している）に間に合うとは思わないが、Java 8では実装されているかもしれない。

Answer 2

関数が自己再帰的である非常に単純な場合のみです。

Proof of tail recursion ability.

スカーラ2.8はしかし、末尾再帰の認識を向上する可能性があるように見えます。

Answer 3

スカラ2.7.xは、最終的なメソッドとローカル関数の自己再帰（自己を呼び出す関数）のテールコール最適化をサポートしています。

スカラ2.8には、相互に再帰的な機能を最適化する技術であるtrampolineのライブラリサポートも付属しています。

Scala再帰の状態に関する多くの情報は、Rich Dougherty's blogにあります。

Answer 4

スカラ座2.8では、あなたは、コンパイラが最適化を願って特定のメソッドをマークする@tailrecを使用することができます。

import scala.annotation.tailrec 

@tailrec def factorialAcc(acc: Int, n: Int): Int = { 
    if (n <= 1) acc 
    else factorialAcc(n * acc, n - 1) 
} 

の方法は、あなたが警告を受ける最適化することができない場合。