4.5 再帰

JavaScriptでは、ユーザー定義関数の中でその関数自身を呼び出す再帰（再帰呼び出し，recursive）ができる。
今回は、階乗 n! やニュートンの近似法を例に、再帰の使い方を学ぶ。

サンプル・プログラム

階乗を求める

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

自然数 n の階乗 n! は、1からnまでのすべての整数の積である。
たとえば6の階乗は　 $mimetex$ 　だが、これをプログラムにするには、一般化した定義（数式）が必要だ。
まず、合計で考えてみよう。階乗 n! は、数学記号の総乗を用いて

$mimetex$

と表すことができる。
これをプログラムにしたものが "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! を計算してみよう。定義は次の通り――。

$mimetex$

これをプログラムにしたものが "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();

再帰は、フラクタル図形を描くときに重宝する。
左図は、「PHPで雪の結晶を描く」で紹介したもの。

左図は、「PHPでマンデブロ集合を描く」で紹介したマンデブロ集合だ。アニメ『フラクタル』のオープニングで記憶に残っている方もいるだろう。

読みやすいプログラム：1関数1機能

1つの関数には1つの機能だけ実装するようにする。
こうすることで、関数の処理の流れが把握しやすく、再利用もしやすくなる。

たとえば、階乗計算を行う関数 factorial は、前半で引数のバリデーションチェックを行い、問題がなければ後半で階乗計算を行う。この階乗計算を行う単一機能を、forループを使った方式のものを factorialLoop、再帰呼び出しのものを factorialRecursive とした。

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

コラム：ループとスパイラル

ループ文と比べて再帰は、螺旋（スパイラル）を描くように上昇していくイメージがあり、格好がいい。
再帰は、数学の帰納法の一種とみなすことができる。帰納法が苦手だった人は少なくないだろう。

解法が分かっていたり業務プロセスが定まっているものをプログラム化するのであれば演繹法でコーディングすれば十分なのだが、不確実性の時代である――帰納的にプログラミングしなければならない局面がある。ディープラーニングもその手段の1つだ。再帰はループに比べてリソースを消費するが、いまどきのパソコンの性能なら問題にはならないだろう。
時間があるときに、帰納法について振り返ってみてほしい。

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

アニメ『天元突破グレンラガン』