末尾再帰

末尾再帰（読み：まつびさいき、英語：tail recursive）とは、再帰のうち、関数の末尾にのみ再帰を記述するプログラミングのテクニックである。

概要

末尾再帰は再帰呼び出しが関数の末尾にのみ登場することをいう。

そんな小難しくて面倒なことをして何が嬉しいかというと、賢いコンパイラだと最適化時に末尾再帰を検出すると自動的に再帰を再帰ではなく展開してくれる。これを末尾再帰最適化といい、スタックを食いつぶすなどの再帰のデメリットをプログラマとコンパイラのコラボレーションで解決してくれる。

例

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

末尾再帰の例としてよく上がる処理

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

• フィボナッチ数
• 階乗

関連項目

• 末尾再帰最適化
• 真正末尾再帰
• 再帰