末尾再帰

提供: MonoBook
ナビゲーションに移動 検索に移動

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

「関数の終わりの一行」ではなく「return直前の再帰処理」が末尾再帰である。ifとelseで分岐しても両方がreturnで終わるなら末尾再帰に該当する。

int func() {
    if (x)
        return recursive1();
    else 
        return recursive2();
}

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

[編集 | ソースを編集]

C#での例。なお、C#では「マイクロソフト製のコンパイラ」で、「ターゲットをx64を指定」し、かつ「Releaseビルド(最適化を有効にした状態でビルド)」を行った場合のみ末尾再帰最適化が行われる。Monoのコンパイラ(msc)でどうなるかは未調査。

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);
    }
}

末尾再帰の例としてよく上がる処理[編集 | ソースを編集]

末尾再帰の記述例は以下を参照。

関連項目[編集 | ソースを編集]