「末尾再帰」を編集中

'''末尾再帰'''（読み：まつびさいき、[[英語]]：tail recursive）とは、ある[[関数]]の最後の1行（return直前）に[[再帰]]を記述する[[プログラミング]]のテクニックである。

「関数の終わりの一行」ではなく「return直前の再帰処理」が末尾再帰である。ifとelseで分岐しても両方がreturnで終わるなら末尾再帰に該当する。
<source lang=csharp>
int func() {
    if (x)
        return recursive1();
    else 
        return recursive2();
}
</source>

賢い[[コンパイラ]]だと[[最適化]]の際にこの末尾再帰を検出すると自動的に「[[再帰]]を[[再帰]]ではない形式に展開」してくれる。これを[[末尾再帰最適化]]といい、[[スタック]]を食いつぶすなどの[[再帰]]のデメリットを[[プログラマ]]と[[コンパイラ]]の[[コラボレーション]]で解決することができる。

=== 例 ===
[[C Sharp|C#]]での例。なお、[[C Sharp|C#]]では「マイクロソフト製のコンパイラ」で、「ターゲットをx64を指定」し、かつ「Releaseビルド（最適化を有効にした状態でビルド）」を行った場合のみ[[末尾再帰最適化]]が行われる。[[Mono]]のコンパイラ（msc）でどうなるかは未調査。
<source lang="csharp">
class TailRecursive 
{
    public int Sum(int n) 
    {
        return SumTailRecursive(n, 0);
    }

    private int SumTailRecursive(int n, int a) 
    {
        if (n < 1) 
        {
            return a;
        }
        // 末尾（関数内で最後に出現するreturn文）
        return SumTailRecursive(n - 1, a + n);
    }
}
</source>

== 末尾再帰の例としてよく上がる処理 ==
末尾再帰の記述例は以下を参照。
* [[フィボナッチ数]]
* [[階乗]]

== 関連項目 ==
* [[末尾再帰最適化]]
* [[真正末尾再帰]]
* [[再帰]]