再帰

再帰 の JavaScript

6個の演習

再帰について

再帰は、関数が自分自身を呼び出す、プログラミングの中でも強力な概念です。最初は少しとらえにくいかもしれませんが、基本を理解すれば、複雑な問題を解くための心強い道具になってくれます。ここからは、わかりやすい例とともに、JavaScriptの再帰を見ていきましょう。

再帰とは?

再帰とは、関数が直接的または間接的に自分自身を呼び出すことです。ループに似ていますが、問題をより小さく扱いやすい部分問題に分解することを伴う場合があります。

例1:カウントダウン

まずはシンプルな例から始めましょう。カウントダウン関数です。

function countdown(num) {
  // Base case
  if (num <= 0) {
    console.log('Blastoff!');
    return;
  }

  // Recursive case
  console.log(num);
  countdown(num - 1);
}

// Call the function
countdown(5);

この例では:

  • 基底ケース:numが0以下になると、関数は"Blastoff!"と出力し、自分自身を呼び出すのをやめます。
  • 再帰ケース:関数は現在のnumを出力し、num - 1を渡して自分自身を呼び出します。

例2:階乗

次に、再帰の定番の例を見てみましょう。数値の階乗を計算します。

function factorial(n) {
  // Base case
  if (n === 0 || n === 1) {
    return 1;
  }

  // Recursive case
  return n * factorial(n - 1);
}

// Test the function
console.log(factorial(5)); // Output: 120

この例では:

  • 基底ケース:nが0または1のとき、関数は1を返します。
  • 再帰ケース:関数はnにn - 1の階乗を掛けます。

重要な概念

基底ケース

すべての再帰関数には、少なくとも1つの基底ケース、つまり自分自身を呼び出すのをやめる条件が必要です。基底ケースがなければ、再帰は無限に続いてしまい、スタックオーバーフローを引き起こします。

再帰ケース

再帰ケースは、問題をより小さく、よりシンプルにした形で、関数がどのように自分自身を呼び出すかを定義します。

再帰の長所と短所

長所:

  • 特定の問題に対しては、エレガントな解決策になります。
  • 数学的帰納法の考え方を模倣しています。

短所:

  • 繰り返しを使った解決策より効率が悪くなることがあります。
  • 再帰が深くなると、スタックオーバーフローを引き起こすことがあります。

まとめ

再帰は、複雑な問題をより小さく扱いやすい部分問題に分解することで単純化する、価値ある手法です。基底ケースと再帰ケースを理解することは、JavaScriptで効果的な再帰的解決策を実装するうえで欠かせません。

さらに学ぶ:

GitHubで編集 リンクは新しいウィンドウまたはタブで開きます

再帰を学習する