最終更新：2026-10-12

C++ 末尾再帰¶

末尾再帰最適化は再帰関数に適用される特殊な最適化技術であり、再帰呼び出しによるスタック領域の使用量を大幅に削減できます。末尾再帰最適化によって、コンパイラは末尾再帰の実行時に新しいスタックフレームの生成を避け、現在のスタックフレームを直接再利用できるため、スタックオーバーフローのリスクを下げ、性能を向上させます。

末尾再帰とは何か？¶

再帰呼び出しが戻る時点で、**他に行うべき操作がない**ような再帰を**末尾再帰**と呼びます。この場合、コンパイラは再帰をループ構造に置き換えることができ、複数回の関数呼び出しのオーバーヘッドを回避できます。

末尾再帰でない例（フィボナッチ数列）¶

次の fibonacci_non_tail() 関数は、標準的な非末尾再帰の実装です：

int fibonacci_non_tail(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_non_tail(n - 1) + fibonacci_non_tail(n - 2);
}

この実装では、再帰呼び出し fibonacci_non_tail(n - 1) と fibonacci_non_tail(n - 2) の後に、それらの結果を加算する必要があるため、これは末尾再帰ではありません。呼び出しのたびに、再帰から戻った後に計算を続けるためのコンテキスト情報を保存する必要があり、その結果スタック領域が急速に増大します。

末尾再帰最適化の例¶

fibonacci_tail() は末尾再帰の方式を利用しています：

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

int fibonacci_tail(int n) {
    return fibonacci_tail_helper(n, 0, 1);
}

ここでの fibonacci_tail_helper() は末尾再帰です。再帰呼び出し fibonacci_tail_helper(n - 1, b, a + b) の後、関数は他に何の作業も必要とせず、再帰呼び出しの結果をそのまま返すことがわかります。したがって、再帰呼び出しは関数の「末尾」に位置しており、再帰呼び出しの後に行うべき余分な操作はありません。

末尾再帰最適化の利点¶

スタック領域の使用量削減：再帰呼び出しのコンテキストを保存する必要がないため、コンパイラはスタックフレームを再利用でき、スタック領域の膨張を回避できます。
スタックオーバーフローの防止：末尾再帰最適化により、非常に大きな再帰の深さに達してもスタックオーバーフローが発生しなくなります。
より高効率：末尾再帰最適化をサポートするコンパイラでは、末尾再帰の性能は反復実装に近く、再帰関数呼び出しのオーバーヘッドが解消されます。

性能テスト¶

最後に上記についてbenchmarkを行ってみたところ、このシナリオでは末尾再帰最適化が非常に有用であることがわかり、性能の差が大きいことが確認できます！