【JavaScript】再帰関数とは?具体例とあわせて解説!

アルゴリズム

再帰関数(recursive function)とは、処理の中で自分自身の関数を呼び出す関数のことです。

再帰関数を使うことで、同じような処理を何度も行う場合に簡潔に記述することができます。

再帰関数の大まかな書き方

ざっくり書くと以下のようなイメージです。

function recursiveFunction() {
  ~処理~
  recursiveFunction();
}



ご覧の通り、recursiveFunction関数の中で、自分自身であるrecursiveFunction関数を呼び出していますね。


しかし、このままだと永久に同じ関数の実行を繰り返してしまうことになるので、再帰を終わらせる処理を追加する必要があります。

function recursiveFunction() {
  if (再帰が終了がする条件) {
    再帰が終了がするときの処理
  }else {
    ~処理~
    recursiveFunction();
  }
}


再帰関数は大まかにこのような形になります。

再帰関数を使った具体例

階乗の計算

では次に、再帰関数を使って自然数の階乗を求める関数をみてみましょう。

コードの導出

念のため階乗の計算の確認ですが、自然数 n の階乗(n!)の求め方は、1から n までの自然数を全て掛けた値になります。


たとえば、
5!=5×4×3×2×1となりますが、
5!=5×4! というように表すこともできます。そして同様に、
4!=4×3!
3!=3×2!
2!=2×1!
1!=1


となりますね。
これを一般化すると、


n! = n × ( n – 1 )!


となります。


そして再帰を終了させる条件は、n = 1 になったときですね。

階乗の計算のこの処理を再帰関数で表すと以下のようになります。

function factorial(n) {
  if (n == 1) {
    return 1;
  }else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5));


本当にただ上の式をそのまま当てはめただけですね(笑)

コンソールで確認すると、きちんと120(=5×4×3×2×1)と表示されます。

コードの解説

factorial( 5 ) を実行

5 × factorial( 4 )

5 × 4 × factorial( 3 )

5 × 4 × 3 × factorial( 2 )

5 × 4 × 3 × 2 × factorial( 1 )

5 × 4 × 3 × 2 × 1


といった流れで繰り返し同じ処理が行われています。

非常にシンプルなコードなのにこのようなループ処理ができるのは面白いですよね。



もっといろいろな再帰関数を使ったプログラムを知りたいという方は、以下の問題集がおすすめです!
(ただし、難易度は高いのでご覚悟を…笑)




ではこの問題集からひとつ、「長方形を分割して正方形をつくる」プログラムを紹介します。

長方形を分割して正方形をつくる

たとえば 8×3 の長方形があった場合、短辺を一辺とする正方形を端からつくっていき、残った形が正方形になるまでこの作業を繰り返すと、最終的に5つの正方形に分割することができます。

今回は、自由に横と縦の長さを設定したときに正方形を何個つくることができるかを返すプログラムをつくってみましょう。

コードの導出

考え方としては、基本は「長辺÷短編」です。

たとえば 9×3 の長方形からは、9÷3 で 3つの正方形をつくることができます。


しかし、もちろん割り切れない場合もありますね。

その場合は、残った長方形に対して同様の処理を行います。


さらにまた割り切れない場合は、残った長方形に対して――


といった流れで、最終的に割り切れるまで同じ処理を繰り返します。

これを再帰関数を使って表すと、以下のようになります。

function cut(width,height) {
  //heightの方がwidthより長い場合は入れ替え
  //(計算の都合上widthの方が長くなるようにする)
  if (height > width) {
    const temp = width;
    width = height;
    height = temp;
  }
  //正方形の個数
  let result = Math.floor(width / height);

  //widthをheightで割ったあとの残り
  const remain = width % height;
  //まだ残りがある場合
  if (remain > 0) {
    //残った縦長の長方形を横向きに変えて同じ処理を繰り返す
    result += cut(height, remain);
  }
  //正方形の個数を返す
  return result;
}

console.log(cut(8,3));

コンソールには、きちんと5と表示されます。

コードの解説

cut(8,3)を実行

result に、8÷3の商である 2 が入る
(正方形が2個できる)

remainに、8÷3のあまりである2が入る
(widthの残りの長さ)

長辺3、短辺2の長方形が残ったため、
result + cut(3,2)が戻り値となる


cut(3,2)を実行

result に、3÷2の商である 1 が入る
(正方形が1個できる)

remainに、3÷2のあまりである1が入る
(widthの残りの長さ)

長辺2、短辺1の長方形が残ったため、
result + cut(2,1)が戻り値となる


cut(2,1)を実行

result に、2÷1の商である 2 が入る
(正方形が2個でき、あまりがないためこれ以上再帰は起きず、2 を戻り値として返す)


cut(3,2)の戻り値
= result + cut(2,1)
= 1 + 2
=3

cut(8,3)の戻り値
= result + cut(3,2)
= 2 + 3
=5

まとめ

再帰関数は考えるのが難しく頭が混乱してしまうかと思いますが、理解できると気持ちいいですよね!


この本でめちゃくちゃ鍛えられるのでおすすめです( `ー´)ノ

コメント

コンタクトフォーム

    タイトルとURLをコピーしました