末尾再帰（Tail Recursion）とは？C++での実装例と最適化の仕組みを解説

本記事では、再帰処理の中でも特に重要な「末尾再帰（Tail Recursion）」について解説します。末尾再帰とは、関数内の最後のステートメントとして再帰呼び出しを行う形式の再帰のことです。再帰呼び出しから戻ってきた後に実行すべき処理が一切残っていない状態が、まさに末尾再帰と呼ばれるものです。

末尾再帰のコード例

以下は、末尾再帰を使ったシンプルなC++のサンプルコードです。引数 n から 0 までの数値を順に出力します。

#include <iostream>
using namespace std;

void printN(int n){
    if(n < 0){
        return;   // ベースケース：負の数になったら終了
    }
    cout << n << " ";
    printN(n - 1);   // 関数の最後で再帰呼び出し → 末尾再帰
}

int main() {
    printN(10);
}

実行結果

10 9 8 7 6 5 4 3 2 1 0

末尾再帰が非末尾再帰より優れている理由

末尾再帰は、非末尾再帰と比較してパフォーマンス面で有利です。その理由は以下の通りです。

• コンパイラによる最適化が容易： 再帰呼び出しの後にやるべき処理が存在しないため、コンパイラはこの再帰をループ構造へと変換（末尾呼び出し最適化）できます。
• スタック領域の節約： 通常、関数が呼び出されると、その戻り先アドレスがスタックに積まれます。しかし末尾再帰の場合、呼び出し後に戻る必要がないため、アドレスをスタックに保存する必要がありません。これにより、深い再帰でもスタックオーバーフローのリスクを大幅に減らせます。

非末尾再帰の例：階乗計算

階乗の計算は再帰で実装できますが、一般的な書き方では末尾再帰にはなりません。次のコードを見てみましょう。

long fact(int n){
    if(n <= 1)
        return 1;
    return n * fact(n-1);   // fact(n-1) の結果を後から掛ける必要がある
}

この実装では、fact(n-1) の戻り値を受け取った後に n を掛けるという「追加の処理」が残っています。つまり、再帰呼び出しが関数の最後の操作ではないため、これは末尾再帰ではありません。

階乗を末尾再帰に書き換える方法

アキュムレータ（累算用の引数）を追加することで、この関数を末尾再帰に変換できます。途中結果を引数として持ち回るのがポイントです。

long fact(long n, long a){
    if(n == 0)
        return a;              // 累積した結果を返す
    return fact(n-1, a*n);     // 最後の操作が再帰呼び出しのみ → 末尾再帰
}

// 呼び出し例：fact(5, 1) → 120

このように書き換えることで、再帰呼び出しの後に何も処理が残らない純粋な末尾再帰となり、コンパイラの最適化対象となります。再帰的な問題を扱う際は、「呼び出し後に追加の計算が必要かどうか」を意識すると、より効率的なコードを書くヒントになります。