再帰アルゴリズムとは?
再帰アルゴリズムとは、関数が自分自身を呼び出して問題を解く手法です。再帰関数は大きな問題を小さな問題に分割し、その部分問題を解くことで最終的に全体の問題を解決します。再帰は、データ構造の探索や階乗、フィボナッチ数列など、さまざまなアルゴリズムに利用されます。
再帰の基本的な構造
再帰関数には、基本的に2つの要素があります。
- ベースケース(終了条件):再帰呼び出しを終了するための条件。これがないと無限ループに陥る。
- 再帰呼び出し:関数が自分自身を呼び出して問題を小さくしていく。
これらを使って、問題を小さく分解し、ベースケースに達したら解を返すことで問題を解決します。
再帰アルゴリズムの実装例
ここでは、再帰アルゴリズムの典型例である「階乗の計算」と「フィボナッチ数列の計算」を紹介します。
階乗の再帰的実装
階乗とは、1からその数までの整数をすべて掛け合わせた値です。例えば、5! = 5 × 4 × 3 × 2 × 1
となります。再帰を使って階乗を計算する方法は以下の通りです。
function factorial(n) {
// ベースケース: nが0または1なら、1を返す
if (n === 0 || n === 1) {
return 1;
}
// 再帰呼び出し: n × (n-1)の階乗を計算
return n * factorial(n - 1);
}
console.log(factorial(5)); // 出力: 120
この関数は、n
が0または1の場合に1を返し、それ以外の場合はn × (n-1)
の階乗を再帰的に計算します。
フィボナッチ数列の再帰的実装
フィボナッチ数列は、次の項が前の2つの項の和になる数列です。例えば、0, 1, 1, 2, 3, 5, 8, 13,...
と続きます。フィボナッチ数列も再帰を使って実装することができます。
function fibonacci(n) {
// ベースケース: nが0なら0、nが1なら1を返す
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
// 再帰呼び出し: 前の2つのフィボナッチ数の和を計算
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(6)); // 出力: 8
この再帰関数は、ベースケースとしてn
が0なら0、1なら1を返し、それ以外の場合は前の2つのフィボナッチ数を足し合わせることで次の値を計算します。
タイル再帰と通常再帰の比較
再帰には、通常の再帰と、再帰呼び出しの結果をすぐに返す形のタイル再帰(Tail Recursion)があります。タイル再帰は、再帰の最終結果を保持する必要がないため、効率的に実行される場合があり、最適化が可能です。
通常の再帰とタイル再帰の比較例
種類 | 説明 |
---|---|
通常の再帰 | 関数の再帰呼び出しが終わった後に他の計算を行う必要がある。再帰の結果が戻るまでスタックを保持する。 |
タイル再帰 | 再帰呼び出しの結果をすぐに返す形式。スタックを保持する必要がなく、最適化されることが多い。 |
タイル再帰による階乗計算
次に、タイル再帰で階乗を計算する例を示します。これにより、再帰呼び出しを行いながら、結果を保持せずに処理を行うことができます。
function tailFactorial(n, total = 1) {
// ベースケース: nが1以下なら、結果を返す
if (n <= 1) {
return total;
}
// タイル再帰: totalに結果を積み重ねていく
return tailFactorial(n - 1, n * total);
}
console.log(tailFactorial(5)); // 出力: 120
このタイル再帰の例では、total
変数を使って中間結果を保持し、再帰的に計算を続けます。これにより、再帰の深さを抑えて効率的に階乗を計算できます。
まとめ
再帰アルゴリズムは、問題を分割して再帰的に解決する強力な手法です。再帰関数には終了条件が重要で、終了条件がないと無限ループに陥る可能性があります。
また、タイル再帰は再帰処理を最適化するための技術であり、特定のケースでは通常の再帰よりも効率的です。再帰アルゴリズムの実装方法を理解し、状況に応じて最適な手法を選択することが重要です。