再帰アルゴリズムの実装 | 再帰関数とタイル再帰 | JavaScript 超完全入門 基本から発展までのすべて

現在作成中です。今後加筆修正してまいります。
スポンサーリンク
スポンサーリンク

再帰アルゴリズムとは?

再帰アルゴリズムとは、関数が自分自身を呼び出して問題を解く手法です。再帰関数は大きな問題を小さな問題に分割し、その部分問題を解くことで最終的に全体の問題を解決します。再帰は、データ構造の探索や階乗、フィボナッチ数列など、さまざまなアルゴリズムに利用されます。

再帰の基本的な構造

再帰関数には、基本的に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変数を使って中間結果を保持し、再帰的に計算を続けます。これにより、再帰の深さを抑えて効率的に階乗を計算できます。

まとめ

再帰アルゴリズムは、問題を分割して再帰的に解決する強力な手法です。再帰関数には終了条件が重要で、終了条件がないと無限ループに陥る可能性があります。

また、タイル再帰は再帰処理を最適化するための技術であり、特定のケースでは通常の再帰よりも効率的です。再帰アルゴリズムの実装方法を理解し、状況に応じて最適な手法を選択することが重要です。

Amazonロゴ
   
ad.価格範囲を指定して商品を探せます。セールで助かる便利ツール
超完全入門
スポンサーリンク
このページをメモ、または、シェア