4.5 再帰

1. サンプル・プログラム
2. 階乗を求める
3. 再帰
4. 再帰の応用
5. 読みやすいプログラム：1関数1機能
6. コラム：ループとスパイラル

ダウンロード

階乗n!を求めるプログラムを作ってみよう。

自然数 n の階乗 n! は、1からnまでのすべての整数の積である。
たとえば6の階乗は　 \( 6!=6 \times 5 \times 4 \times 3 \times 2 \times 1=720 \)　だが、これをプログラムにするには、一般化した定義（数式）が必要だ。
まず、合計で考えてみよう。階乗 n! は、数学記号の総乗を用いて
\[ \displaystyle n! = \prod_{k=1}^{n} k = n \times (n-1) \times \cdots \times 3 \times 2 \times 1 \]
と表すことができる。
これをプログラムにしたものが "factorial1.html" である。

factorial1.html を実行

  36: /**
  37:  * forループを用いた階乗計算
  38:  * @param   Number n
  39:  * @return  Number 階乗
  40: */
  41: function factorialLoop(n) {
  42:     let ret = 1;
  43:     for (let i = n; i >= 1; i--) {
  44:         ret *= i;
  45:     }
  46:     return ret;
  47: }

ユーザー定義関数 factorialLoop が、上記の定義（数式）をそのまま実装したものである。forループを回して合計計算を行っている。

  49: /**
  50:  * 階乗計算を行う．
  51:  * @param   Number n
  52:  * @return  Number 階乗／(-1)：引数エラー
  53: */
  54: function factorial(n) {
  55:     let ret;
  56: 
  57:     //引数をバリデーションチェックする．
  58:     if (! Number.isInteger(n)) {
  59:         ret = (-1);
  60:     } else if (n < 1) {
  61:         ret = (-1);
  62: 
  63:     //階乗計算を行う．
  64:     } else {
  65:         ret = factorialLoop(n);
  66:     }
  67: 
  68:     return ret;
  69: }

ユーザー定義関数 factorial は、階乗計算関数で、前半の2つの if～else文は、引数が自然数かどうかをチェックしている。自然数であれば、factorialLoop を呼び出す。

プログラムで言う再帰（再帰呼び出し，recursive）とは、たとえばユーザー定義関数の中でその関数自身を呼び出す手法である。再帰ができる言語とそうでない言語があるが、JavaScriptは再帰ができる。

そこで、再帰を使って階乗 n! を計算してみよう。定義は次の通り――。
\[ \displaystyle \left\{\begin{array}{ll}1, & if \quad n = 0 \\n \times (n - 1)!, & if \quad n > 0\end{array}\right. \]

これをプログラムにしたものが "factorial2.html" である。

factorial2.html を実行

  36: /**
  37:  * 再帰呼び出しを用いた階乗計算
  38:  * @param   Number n
  39:  * @return  Number 階乗
  40: */
  41: function factorialRecursive(n) {
  42:     if (n === 1) {
  43:         ret = 1;
  44:     } else {
  45:         ret = n * factorialRecursive(n - 1);    //再帰呼び出し
  46:     }
  47: }

ユーザー定義関数 factorialRecursive が、上記の定義（数式）をそのまま実装したものである。factorialLoop と異なり、ループ文がなくなっており、代わりに引数を変えて factorialRecursive 自身を呼び出している。

再帰 の効果は、パラメータが刻々と変わっていくようなループ文に対して用いると、プログラムを単純化できることだ。
そこで、「3.4 whileループ」で紹介したニュートン法を用いた近似計算に再帰を適用してみよう。

sqrtByNewton.html を実行

  36: /**
  37:  * ニュートン法で平方根を求める（再帰）
  38:  * @param   Number x 計算中の平方根
  39:  * @param   Number y 元のyの値
  40:  * @param   Number e 誤差
  41:  * @return  Number 平方根
  42: */
  43: function sqrtByNewton(x, y, e) {
  44:     //ニュートン法で新しいyを求める
  45:     let x2 = x - (x * x - y) / (x * y);
  46: 
  47:     //誤差範囲より大きければ再帰
  48:     if (Math.abs(x2 - x) >= e) {
  49:         x2 = sqrtByNewton(x2, y, e);
  50:     }
  51: 
  52:     return x2;
  53: }

比較のために、whileループによるニュートン法を再掲する。

  37:         //平方根計算
  38:         let x = y * 2;      //xの初期値
  39:         while (true) {
  40:             //ニュートン法で新しいyを求める
  41:             let x2 = x - (x * x - y) / (x * y);
  42:             //誤差範囲内になったら計算終了
  43:             if (Math.abs(x2 - x) < e)    break;
  44:             //x←x2として計算を繰り返す
  45:             x = x2;
  46:         }
  47:         root = '近似値 = ' + x.toString();

関数 factorial の中の1行を変更するだけで、この2つの方式を切り替えることができる。
また、とくに factorialRecursive は自分自身を再帰呼び出しするので、単一機能でなければならない。

俺達は1分前の俺達よりも進化する。1回転すれば、ほんの少しだが前に進む。
それがドリルなんだよ❗