.net - 決定的なテールコール再帰問題

Question

この大失敗の質問の討論に参加した後、私はコミュニティ全体の前で質問を提起したいと思います.

末尾呼び出しの最適化は、.Net ベースのコードにどのようなシナリオで適用されますか?

信頼できる最新の情報源または再現可能な実験で回答をサポートしてください。

Answer 1

Don Syme らによって書かれた "Expert F#" によると、F# は末尾呼び出しの最適化を行います。Eric Lippert のブログで、C# コンパイラ (どのバージョンでも) には含まれていないことを読んだことを覚えているようです。間違っていたら訂正してくれ、エリック。いずれの場合も、最後の命令がメソッドを呼び出すときに末尾呼び出しの最適化を行うことができます。これは多くの場合、メソッド自体の再帰呼び出しになりますが、そうである必要はありません。現在のスタック フレームが不要になることが保証されているため、最適化を行うことができます。ただし、後で簡単な操作を実行する必要がある場合は、最適化を実行できません。

int Fib(int n)
{
  if(n < 2)
     return 1;

  return Fib(n-1) + Fib(n-2);
}

これは、 への最後の呼び出しが戻る+前に評価できないため、末尾呼び出しの最適化はできません。Fib(実際、これはExpert F#でも使用されている例だと思いますが、それについてはわかりません。)

int Fib(int n, int a, int b)
{
  if(n == 0)
    return a+b;
  return Fib(n-1,a+b,a);
}

このバージョンは、すべての引数がFib への最後の呼び出しの前に評価され、呼び出しの後に実行される操作が存在しないため、最適化された末尾呼び出しである可能性があるため、現在のスタック フレームを破棄できます。