Chapter 64

再帰

miku
miku
2021.11.17に更新

関数内で自身の関数を呼ぶことを再帰呼び出しと呼ぶ。再帰はフラクタルや矩形分割などジェネレーティブアートの分野などで非常によく使われるテクニックなのでまずは基本をここで解説する。

再帰

function f() {
  f();
}

再帰とは要はこういう形のことだ。このままだと無限ループになるので実際にはもう少し処理を加える必要があるがそれについては後述する。

再帰が利用されるのは手順が同じだがパラメータが毎回変わるという場面が多い。たとえば円を描画する場面で考えてみよう。

function setup() {
  createCanvas(windowWidth, windowHeight);

  drawCircle(0);
}

function drawCircle(x) {
  circle(x, height / 2, 40);
  x += 100;
  drawCircle(x);
}

drawCircle() は、引数 x の位置に円を描画して、x の値を増やし、また drawCircle() を呼び出すという再帰関数だ。最初に渡した引数が 0 で、増える値が 100 なので、0→100→200→300...のx座標に円が描画される。

実際に実行してみるとこれは無限ループになる。forwhile のようなループ処理を利用する場面と同じで再帰にも終了条件が必要だ。

終了条件を付ける

function setup() {
  createCanvas(windowWidth, windowHeight);

  drawCircle(10, 0);
}

function drawCircle(n, x) {
  if (n === 0) {
    return;
  }

  circle(x, height / 2, 40);
  x += 100;
  drawCircle(n - 1, x);
}

drawCircle() の第一引数に n を付けた。これはループの残り回数で、関数内の drawCircle() には n - 1 を指定して n の値を減らしていく。そして n0 になったら return でこれ以上再帰呼び出しさせないようにする。

再帰の中の複数の再帰

function setup() {
  createCanvas(windowWidth, windowHeight);

  drawCircle(10, 0, 0);
}

function drawCircle(n, x, y) {
  if (n === 0) {
    return;
  }

  circle(x, y, 40);
  drawCircle(n - 1, x + 100, y);
  drawCircle(n - 1, x, y + 100);
}

右に移動した場合の n = 9 と下に移動した場合の n = 9 があり、そこから更に n = 8 の分岐が増えていく。

再帰の呼び出し回数

let i = 0;
function setup() {
  createCanvas(windowWidth, windowHeight);

  drawCircle(10, 0, 0);
  console.log(i);
}

function drawCircle(n, x, y) {
  i++;

  if (n === 0) {
    return;
  }

  circle(x, y, 40);
  drawCircle(n - 1, x + 100, y);
  drawCircle(n - 1, x, y + 100);
}

関数の呼び出し回数を測るため、変数 i を用意して、再帰関数の先頭で値を増やしていく。再帰終了後に実行してみると、n = 10 のとき、i は 2047 になる。

なぜこんな大きな呼び出し回数になるのか。

最初の関数呼び出し、つまり n = 10 のときは1回、その中で n-1 が2回、その2回の中で更に2回呼び出されるので4回...と n が減るたびに倍々に呼び出される関数が増えていく。

n 再帰呼び出し回数 累計
10 1 1
9 2 3
8 4 7
7 8 15
6 16 31
5 32 63
4 64 127
3 128 255
2 256 511
1 512 1023
0 1024 2047

累計の回数は 2のべき乗 - 1 の形になっている。引数に n を指定したときは 2^{n + 1} - 1 回だ。適当に n = 30 とかに設定してしまうと、再帰呼び出しの回数が10億を超える。

このように n の値には注意しなければならないのだが、場合によっては計算回数を大幅に減らすことができる。

再帰で右あるいは下に移動する場合、3回目の呼び出しで位置が被ることが図でわかるだろう。この場合、被っていても次も全く同じ位置に円を描くので無駄な再帰呼び出しになる。

解決方法としては、座標を記憶しておき、後に同じ座標が出てきた場合はスキップするという方法だ。このような技法をメモ化再帰と呼ぶ。

メモ化再帰

function drawCircle(n, x, y) {
  if ((x, y)位置が過去に実行されていたら) return;
  (x, y)位置を記憶

  今までのコード...
}

メモ化再帰をコードで書くと上記のような形になる。実際に座標を記憶する方法だが、たとえば配列に入れておくなどが考えられる。ただ、配列内の座標と今の座標を比較にするには配列内の要素と一つ一つ比較していく必要があるが、最悪配列のサイズ分だけ比較する必要があるので、あまり効率的ではない。できれば座標を渡したらすぐに記憶されているかが知りたいところだ。

このようなデータ構造として連想配列がある。

function createKey(x, y) {
  return x + " " + y;
}

let seen = {};
seen[createKey(2, 3)] = true;

console.log(seen[createKey(2, 3)]); // true
console.log(seen[createKey(2, 4)]); // undefined
console.log(seen[createKey(3, 3)]); // undefined

連想配列のキーには (2, 3) のような複数の数値を指定できないので、座標を一つの文字列に変換したものをキーにする。

let seen;

function setup() {
  createCanvas(windowWidth, windowHeight);

  seen = {};

  drawCircle(10, 0, 0);
}

function createKey(x, y) {
  return x + " " + y;
}

function drawCircle(n, x, y) {
  const key = createKey(x, y);
  if (seen[key]) return;
  seen[key] = true;

  if (n === 0) {
    return;
  }

  circle(x, y, 40);
  drawCircle(n - 1, x + 100, y);
  drawCircle(n - 1, x, y + 100);
}

n = 10 のとき、再帰関数が2047回呼ばれていたが、メモ化再帰のおかげで111回まで減った。

n 通常の再帰呼び出し回数 メモ化再帰の呼び出し回数
10 2047 111
20 2097151 421
30 2147483647 931
40 2199023255551 1641
50 2251799813685247 2551

今回は被った位置から次の移動位置が同じなので、メモ化が有効になるが、たとえば移動位置がランダムなどのような場合にメモ化をすると単に描画の量が減ってしまうので有効でなくなる場合がある。メモ化の利用は適材適所だということだ。