再帰呼び出し 【プログラミング発展】

再帰呼び出しは、関数が自分自身を呼び出すことです。このような関数を再帰関数と呼びます。

例

function factrial(a) {
    if (a < 0) return null;
    if (a == 0 || a == 1) return 1;

    // ここで再帰呼び出し
    if (a > 1) return a * factrial(a - 1);
}

console.log(factrial(5));

120

factrialは階乗という意味です。つまり、factrial(5)は5!を計算しています。

ここで、if (a > 1) return a * factrial(a - 1);で、factrialがfactrialを呼び出していますね。これが再帰呼び出しです。

そのままでは理解しづらいので、実際の処理順を考えてみます。

1. factrial(5)を呼び出す
   1. a > 1なので、a * factorial(a - 1)を実行
   2. factrial(4)を呼び出す (a - 1は4)
      1. a > 1なので、a * factorial(a - 1)を実行
      2. factrial(3)を呼び出す
         1. a > 1なので、a * factorial(a - 1)を実行
         2. factrial(2)を呼び出す
            1. a > 1なので、a * factorial(a - 1)を実行
            2. factrial(1)を呼び出す
               1. a == 1なので, return 1する
            3. factrial(1)が1なので、a * factrial(a - 1)は2 * 1で2
         3. factrial(2)は2なので、a * factrial(a - 1)が3 * 2で6
      3. factrial(3)は6なので、a * factrial(a - 1)が4 * 6で24
   3. factrial(4)は24なので、a * factrial(a - 1)が5 * 24で120
2. factrial(5)の計算結果は120

という感じです。見事に階層構造になっていることがわかりますね。

再帰関数は、ループ処理の1つです。そのため、forやwhileなどとの置き換えが可能です。

注意点など

再帰呼び出しを行う際は、次のことに注意する必要があります。

• 呼び出し階層が深すぎるとスタックオーバーフローを起こしたり、エラーとなる場合がある
  メモリ量や言語によって異なりますが、少なくとも1000は耐えるはずです
• for文などより遅い
  数万や数十万回再帰呼び出すような、ループ回数が多い場合は気にしたほうが良いです。
• while(1)等と同様に無限ループしやすい

その他、次のような特徴があります。

• すべての再帰呼び出しは、for文やwhile文など、他のループに置換できる
• for文やwhile文より簡潔に書ける場合がある (DFSやDPなどの一部)

再帰呼び出しは、どんどん書いて慣れていく必要があります。再帰呼び出しを理解することで、プログラムの関数の挙動、代入の挙動、アルゴリズム力など数多くの要素を鍛えることができます。

まずは階乗などのかんたんな例からはじめ、慣れてきたら深さ優先探索(DFS)など、実用的なアルゴリズムをかけるように練習してみましょう!

まとめ

再帰呼び出しは、関数が自分自身の関数を呼び出す行為です。使う際にはいくつかの注意点があるため、気をつけて使う必要があります。

練習し、理解していくことでプログラムそのものの動きの理解を進めていきましょう!