Cプログラムにおける再帰関数の補助空間とは？

はじめに

本記事では、C言語における再帰関数の呼び出しに必要な補助空間（オーバーヘッド）について解説します。さらに、通常の関数呼び出しと比較して、どのような違いがあるのかを見ていきましょう。

再帰関数の例

まず、以下のような階乗を求める関数を考えてみます。

long fact(int n){
    if(n == 0 || n == 1)
        return 1;
    return n * fact(n-1);
}

この fact() 関数は、自分自身を呼び出しているため再帰関数です。

再帰呼び出し時のスタックの動き

この関数を fact(5) のように呼び出すと、各呼び出しの戻り先アドレスがスタック上に次々と積まれていきます。

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

再帰関数は自分自身を何度も呼び出すため、呼び出しごとに新しいスタックフレーム（戻り先アドレスやローカル変数など）がスタックに追加されます。その結果、関数が n 回再帰的に呼び出された場合、補助空間は O(n) 必要になります。

通常の関数呼び出しとの違い

ここで注意したいのは、「同じ関数を n 回呼び出せば必ず O(n) の空間が必要になる」というわけではない点です。

通常の関数の場合、呼び出し時には一時的にアドレスがスタックへプッシュされますが、処理が完了するとすぐにそのアドレスはスタックからポップされ、呼び出し元の関数へ制御が戻ります。その後、次の呼び出しが行われるため、いずれの時点でもスタック上には1つ分のフレームしか存在しません。

この仕組みにより、通常の関数呼び出しを繰り返しても補助空間は常に一定であり、O(1) で済みます。

まとめ

• 再帰関数：呼び出しごとにスタックフレームが残るため、n 回の再帰で補助空間は O(n)
• 通常の関数：完了ごとにスタックから解放されるため、繰り返し呼び出しても補助空間は O(1)

再帰を使う場合は、深い再帰によってスタックオーバーフローが発生する可能性もあるため、再帰の深さとメモリ使用量には十分注意しましょう。