プログラムの中で規則的に行いたいタスクを作成する場合、for文のような反復処理が使えます。
一方で、再帰と呼ばれる仕組みを使うことでタスクをより単純化できる場合があります。

今回は、再帰の考え方や再帰関数の書き方について解説していきます。

再帰関数

そもそも再帰関数とは、関数の中で自分自身を呼び出す関数のことです。また、そのような関数呼び出しの仕組みを再帰と表現します。

function sayHi() {
  sayHi() // 関数自身を呼び出す
}

sayHi();

再帰関数は、例えば計算結果を保存しておき、その計算結果を元に新しい計算を行いたい時になどに使えます。それは、少ないコードでタスクを単純化することができるということです。

再帰の考え方

再帰の仕組みは、単純な階乗やフィボナッチ数の計算から、複雑なアルゴリズムなどに活用されています。

ここでは考え方を理解するために、まずはシンプルな例として階乗の計算を行なってみましょう。

階乗とは、1からある数までの連続する整数の積のことです。
階乗は数学では「n!」と表記され、1からnまでの連続するn個の整数を掛け合わせた値をnの階乗と表現します。

1! = 1   (1の階乗）
2! = 2   (2の階乗）
3! = 6   (3の階乗）
4! = 24  (4の階乗）
5! = 120 (5の階乗）

各値の階乗は、次のように自分自身の値nから1までのすべての値を掛けることによって求めることができます。

1! = 1   
2! = 2 × 1 = 2 
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 5 × 4 × 3 × 2 × 1 = 120

JavaScriptで階乗を求めるには、主に2つの方法があります。

1つ目は反復処理による計算です。
再帰との違いが分かるように、はじめに反復処理での計算を見てみましょう。以下はfor文で階乗を計算したコードです。

function factorial(n) {
  let result = 1;

  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorial(5)); // 120

一番小さい階乗の値は1となるため、変数resultに初期値1を指定します。
その後1からnまでの間resultとnの値を掛け、その結果をresultに代入しその処理を繰り返します。これで階乗を求めることができます。

では、次に再帰的な方法で再現してみます。

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

console.log(factorial(4)); // 24

再帰定な計算のポイントは以下です。

  • nが1以下の場合、nの階乗は1となる
  • そうでない場合、n * factorial(n - 1)で自分自身を呼び出す

例えば、factorial(4)が呼び出された場合（4の階乗）、次のステップを踏みます。

1. 4 * factorial(3) 
2. 4 * (3 * factorial(2)) 
3. 4 * (3 * (2 * factorial(1)))

このように、関数factorialは、nが1に到達するまで再帰的に自分自身の関数を呼び出し、階乗を求めることができます。

再帰関数の書き方

ここでは、再帰関数の書き方について見ていきましょう。

再帰関数では、自分自身を呼び出さない基本のケースと、自分自身を呼び出して再帰的な処理を行うケースに分けて書きます。

function recursion() {
  if(条件式) {
    基本ケース
  } else {
    再帰ケース
  }
}

先ほどの階乗の計算で扱った再帰関数も2つのケースに分けることができます。

                if n <= 1 = 1
                /
factorial(n) = 
                \ 
                else = n * factorial(n - 1)

では、もう一度関数factorialを組み立ててみましょう。
基本ケースとなるのは、nが1以下である場合です。nが1以下であれば、必然的にnの階乗は1になるためです。

function factorial(n) {
  if (n <= 1) {
    return 1 // 基本ケース
  }
}

もう一つのケースは、nが2以上になる場合です。

function factorial(n) {
  if () {
    ...
  } else {
    return n * factorial(n - 1); // 再帰ケース
  }
}

再帰ケースでは、factorial(n - 1)によって、nが1ずつ減少していきます。そのため、nが1以下になった時点で、それまでの値を返すことができます。

基本となるケースがなかったり、条件がずっと変わらない場合には、再帰関数がずっと繰り返されてしまいます。そのため、無限ループとならないように、自分自身の呼び出しを終了するための記述を書くことが必要です。

フィボナッチ数の再帰関数

フィボナッチ数列とは、はじめの2つが1で、それ以降は「直前の2つの数を足した数」という規則を表した数列のことです。また、この数列に並ぶ数のことをフィボナッチ数を呼びます。

1 1 2 3 5 8 13 21 34 55 89 144 ...

この規則から、n番目のフィボナッチ数Fnを出すためには、このように表すことができます。

F0 = 0 
F1 = 1 
Fn = Fn-1 + Fn-2

では、最後に、ここまでのおさらいとしてフィボナッチ数の計算を行なう再帰関数を作成してみましょう。

function fibo(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibo(n-1) + fibo(n-2);
  }
}

console.log(fibo(9)); // 34

関数のポイントは以下です。

  • nが0の時は0、1の時は1を返す = つまりnが1以下の時は自分自身の値を返す
  • それ以外の時は、関数fiboを再帰呼び出しする

関数を実行すると、34という9番目のフィボナッチ数の値が返されます。

まとめ

今回は、再帰の考え方や再帰関数の書き方について解説しました。

// ポイント
* 再帰関数は、関数の中で自分自身を呼び出す関数のこと
* 階乗やフィボナッチ数の計算で再帰が用いられる
* 再帰関数は、基本ケースと自分自身を呼び出す再帰ケースに分けて作成する
* 基本ケースがない、または基本ケースに到達しない場合、無限ループとなる

再帰関数の関連記事

・条件分岐 -if文
・繰り返し処理 -for文