20

時々、末尾再帰関数を書いていることに気づきます。高低を検索していて、.NET Frameworkに末尾再帰があることがわかりましたが、どのような場合に有効で、どのような場合に末尾再帰を効率的に使用できないのかわかりません。たとえば、私は単純な木を持っています、それを呼びましょう

public class Tree
{
  public Tree parent = null;

  public Tree(Tree parent)
  {
    this.parent = parent;
    this.children = new List<Tree>();
  }

  public List<Tree> children {get; private set;}

  public Tree root
  {
    get
    {
      return this.parent == null ? this : parent.root;
    }
  }
}

rootプロパティの場合、コンパイラはループを発行しますか？.tailを放出しますか？ジッタは.tailを尊重しますか？特別なことは何も起こらず、アルゴリズムは再帰的に実行されるだけでしょうか？最も重要なことは、これを反復的に書き直す必要がありますか？

4

2 に答える 2

9

C＃コンパイラはtailプレフィックスを発行しません。

呼び出しがテール位置にある場合、F＃はそうします。末尾再帰が適用可能かどうかは、ツリーをトラバースする順序によって異なります。

あなたのコードでは、テールポジションには何もありません。その理由は、三項演算子の使用です。各ブランチが返されるステートメントを使用するようにコードが書き直された場合、iftoの呼び出しparent.rootはテール位置になります。

最適化に関しては、コンパイラー（F＃またはIronScheme）は通常、末尾再帰呼び出しをwhile (true) { ... }ループに変換します。これは、末尾呼び出しとメソッドを再度呼び出す必要性の両方を取り除くために行われます。

したがって、C＃が末尾呼び出しを発行することを許可された場合（そうではありません）、次のように変換される可能性があります。

public Tree root
{
  get
  {
    if (parent == null) return this;
    else return parent.root; // now in tail position
  }
}

に（ただのゲスト）

public Tree root
{
  get
  {
    Tree temp = this;
    while (true)
    {
      if (temp.parent == null)
      {
         return temp;
      }
      temp = temp.parent;
    }
  }
}

F＃とIronSchemeはどちらも同じ変換を行います。これはtail call elimination（TCE）と呼ばれます。はい、C＃バージョンよりもわずかに高速になります。（私はこれfibをC＃、F＃、IronSchemeのマイクロベンチマークでテストしました）

于 2012-12-19T11:31:13.113 に答える
1

他の答えも同様の答えがあります。

速度について。末尾再帰の最適化は、小さな関数のループと実際には違いはありません。末尾呼び出しの最適化が実行されると、「call」命令（x86上）を「jmp」に置き換えるだけです。同じスルーループを実行すると、次のサイクルに入るための同じ「jmp」命令があります。覚えておくべき1つの瞬間は、関数の本体全体がサイクルの本体になるため、再帰関数のサイズを最小化するように努める必要があるということです。

于 2012-12-19T11:59:19.130 に答える