再帰関数を利用する

再帰関数とは関数内で自分自身の関数を呼びだすことです。ここでは JavaScript における再帰関数の使い方と具体的にどのようなケースで利用できるのかについて解説します。

(Last modified: 2024-09-16)

再帰関数の記述方法
再帰関数の具体的な利用方法

再帰関数の記述方法

再帰関数とは関数内から自分自身の関数を呼びだすことです。次の例を見てください。

function test(){
  test();
}

test();

関数 test は関数内で自分自身である test 関数を呼びだしています。このように関数内で自分自身の関数を呼びだす関数のことを再帰関数といいます。

再帰関数を利用する場合の明確なルールがあるわけではありませんが、無限ループにならないようにこの条件になったら自分自身の呼び出しを終了するような記述が必要となります。次のサンプルを見てください。

function test(){
  if (条件式) {
    test();
  }

  return;
}

test();

この例では条件式を満たしている間は自分自身である test 関数を再帰的に呼び出しますが、条件式を満たさなくなったら自分自身を呼び出すのをやめて関数を終了します。より具体的な例として次のサンプルをみてください。

function test(n){
  console.log('Hello');

  if (n != 0) {
    test(n - 1);
  }

  console.log('Bye');
}

test(2);

>> Hello
>> Hello
>> Hello
>> Bye
>> Bye
>> Bye

この場合は次のような処理が順に行われます。

 1) test 関数(1)が呼び出される。引数として 2 が渡される。
 2) Hello が出力される
 3) test 関数(1)内の条件式は 2 != 0 となり true となる
 4) test 関数(2)が呼び出される。引数として 1 が渡される
 5) Hello が出力される 
 6) test 関数(2)内の条件式は 1 != 0 となり true となる
 7) test 関数(3)が呼び出される。引数として 0 が渡される
 8) Hello が出力される 
 9) test 関数(3)内の条件式は 0 != 0 となり false となる
10) Bye が出力される 
11) test 関数(3) が終了する
12) Bye が出力される 
13) test 関数(2) が終了する
14) Bye が出力される 
15) test 関数(1) が終了する
16) 最初に関数を呼びだした次の処理へ移る

結果としてコンソールには Hello が 3 回 Bye が 3 回出力されます。このように関数が再帰的に呼び出されるたびに条件式が変化していき、最終的に再帰的に関数を呼びださなくなります。最後の関数呼び出しが終了すると、その関数呼び出しを行った次の処理へ進み、結果的に順番に関数の呼び出しが終了していきます。最後に一番最初に呼び出された関数の呼び出しが終了し、関数を呼びだした次の処理へ移ります。

もし再帰関数の処理の流れが分かりにくい場合は、次のような同じ処理を行う関数がいくつもある場合を考えてみてください。

function testC(n){
  console.log('Hello');

  if (n != 0) {
//    testD(n - 1);
  }

  console.log('Bye');
}


function testB(n){
  console.log('Hello');

  if (n != 0) {
    testC(n - 1);
  }

  console.log('Bye');
}

function testA(n){
  console.log('Hello');

  if (n != 0) {
    testB(n - 1);
  }

  console.log('Bye');
}

testA(2);

最初に関数 testA を呼び出し、関数 testA 内で関数 testB を呼び出し、関数 testB 内で関数 testC を呼び出します。関数 testC 内では条件式が false となるためそれ以上他の関数を呼びだすことはなく、呼び出された順に関数の処理が終了していきます。

再帰関数とは、このように同じ処理を行う関数を複数記述する代わりに自分自身の関数を呼びだすことです。慣れないと処理の流れが分かりにくいですが、自分自身と同じ関数が別にあってそれを呼び出していると考えると分かりやすいかもしれません。

再帰関数の具体的な利用方法

再帰関数は簡単な階乗の計算などから複雑なアルゴリズムの解決方法まで幅広い利用がされていますが、今回は階乗の計算を例に愚弟的な利用方法についてみていきます。

階乗というのは例えば数値の 5 の階乗を計算すると 5 * 4 * 3 * 2 * 1 = 120 を求めるものです。これを再帰関数を使って計算すると次のようになります。

function calc(n){
  if (n == 0){
    return 1;
  }

  return n * calc(n - 1);
}

console.log(calc(5));
>> 120

今回のサンプルでは関数が呼び出されるたびに次のような計算が行われていきます。

 1) 関数の戻り値として 5 * calc(4) を計算するため calc(4) が呼び出される
 2) calc(4) が呼び出され 4 * calc(3) を計算するため calc(3) が呼び出される
 3) calc(3) が呼び出され 3 * calc(2) を計算するため calc(2) が呼び出される
 4) calc(2) が呼び出され 2 * calc(1) を計算するため calc(1) が呼び出される
 5) calc(1) が呼び出され 1 * calc(0) を計算するため calc(0) が呼び出される
 6) calc(0) が呼び出され return 1 が実行される
 7) return 1 * 1 が実行される
 8) return 2 * 1 * 1 が実行される
 9) return 3 * 2 * 1 * 1 が実行される
10) return 4 * 3 * 2 * 1 * 1 が実行される
11) return 5 * 4 * 3 * 2 * 1 * 1 が実行される
12) 120 がコンソールに出力される

関数内の戻り値を計算するところで自分自身である関数を呼びだしています。条件式が true となるまで再帰的に関数が呼び出され、再帰関数の呼び出しが行われなくなった時点で順に戻り値が計算されていき、最終的な結果が呼び出し元に戻ります。

今回のような階乗の計算は再帰関数を使用しなくても計算が行えますが、再帰関数の使い方を覚えておくと極めて簡潔に処理を記述できる場合があります。

-- --

JavaScript における再帰関数の使い方と具体的にどのようなケースで利用できるのかについて解説しました。

( Written by Tatsuo Ikura )

著者 / TATSUO IKURA

これから IT 関連の知識を学ばれる方を対象に、色々な言語でのプログラミング方法や関連する技術、開発環境構築などに関する解説サイトを運営しています。