データ構造における再帰の原則

再帰とは何か

再帰（recursion）とは、関数が自分自身を呼び出すプロセスのことです。大きな問題をより小さな部分問題に分割して解決するために用いられます。ただし、再帰的アプローチが有効なのは、各部分問題が同じパターンに従っている場合のみであるという点に注意が必要です。

ベースケースと再帰ケース

再帰関数には、大きく分けて2つの部分が存在します。1つは「ベースケース」、もう1つは「再帰ケース」です。

ベースケースは、再帰の処理を終了させるための条件です。ベースケースが定義されていない場合、関数は理論上、無限に再帰を繰り返すことになります。

再帰と内部スタックの仕組み

コンピュータプログラムでは、ある関数を呼び出すとき、関数の領域へジャンプする前に、プログラムカウンタの値が内部スタックに保存されます。関数の処理が完了すると、保存されたアドレスがスタックから取り出され（ポップされ）、プログラムカウンタに代入されることで、元の処理が再開されます。

再帰呼び出しでは、このアドレスの保存が何度も行われ、次々と関数呼び出し文へジャンプしていきます。ベースケースが定義されていないと再帰が際限なく繰り返され、スタックにアドレスが蓄積され続けます。スタックに空きがなくなると、「Internal Stack Overflow（内部スタックオーバーフロー）」というエラーが発生します。

階乗計算による再帰の例

再帰呼び出しの代表的な例が、数値の階乗を求める処理です。数値nの階乗 n! は n * (n-1)! と等しく、さらに展開すると n * (n - 1) * (n - 2)! と表せます。

つまり、階乗を関数として定義すると、引数が1ずつ減りながら同じ関数が何度も呼び出されることになります。そして引数が1または0になったときに1を返します。これが再帰のベースケースとなります。

コード例

#include<iostream>
using namespace std;
long fact(long n){
    if(n <= 1)
    return 1;
    return n * fact(n-1);
}
main(){
    cout << "Factorial of 6: " << fact(6);
}

出力結果

Factorial of 6: 720

このように、再帰を活用することで、階乗のような繰り返し構造を持つ問題を簡潔に記述できます。ただし、必ず適切なベースケースを設定し、スタックオーバーフローを防ぐことが重要です。