再帰とメモ化 — メモを1行足したら一瞬で終わった

再帰とメモ化。枝分かれした処理カードと計算結果を覚える引き出し、時計。

メモを1行足すだけで、終わらない計算が一瞬で終わります。再帰とメモ化を実装して、その差を測ります。

前回: 最短経路アルゴリズム — ダイクストラは負の重みで壊れる

これは【深掘り】の記事です。本線の順路ではありません。 このシリーズは言葉を覚える回にしません。 全部、手元で書いて、走らせて、数字を出します。 飛ばしても本線は進めます。 本線側の計算量の話は 1万件で100倍になる — 計算量とO記法を測る にあります。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。VM の立て方は VMを29台溜めた話 — Ubuntu Serverの立て方 にあります。


フィボナッチ数列を、教科書どおりに書きました。

function fib(n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
console.log(fib(45));

返ってきませんでした。

30秒待ちました。1分待ちました。エラーも出ません。CPU が1コアだけ 100% に張り付いたまま、何も起きません。

最初に疑ったのは無限ループでした。違いました。 n はちゃんと減っていて、n < 2 で止まります。論理は完全に正しいのです。

n を小さくして試したら、正体が見えました。

fib(30) = 832040     15.9 ms
fib(35) = 9227465   160.1 ms
fib(40) = 102334155 2133.4 ms

5 増やすたびに、およそ11倍になっています。 この調子だと fib(45) は 2秒 × 11 で 23秒、fib(50) は4分、fib(60) は8時間です。

正しく書いたのに、使いものにならない。

原因は再帰そのものではありませんでした。同じ fib(30) を、何百万回も計算し直していただけです。

この記事では、それを実際に数えて、1行足して殺すところまでやります。 そのうえで、再帰がいちばん効く場所 — バックトラック(N-Queen・ナイトの巡回)と、ナップサックをやります。

対象レベル: 中級〜上級 / 区分: 発展

目次

この記事でわかること

  • 再帰に必要なのは2つだけ。 「終わる条件」と「1段小さくして自分を呼ぶ」以外は要らない
  • 終わる条件を忘れると Maximum call stack size exceeded。 これは無限ループではなくスタックの枯渇
  • 素朴な再帰が遅い原因はほぼ「同じ引数の再計算」。 fib(35) は2,986万回呼ばれている
  • メモ化は3行。 Map に覚えさせるだけで、呼び出し回数が n に比例まで落ちる
  • JavaScript に末尾呼び出し最適化は無い。 仕様にはあるが V8 は実装していない。「末尾再帰だから安全」は成立しない
  • バックトラックは「置く → 進む → だめなら戻す」。 そして枝刈りが全部
  • 探す順番を変えるだけで、探索量が桁で変わる(ワーンスドルフの規則で825万手 → 64手)
  • メモ化再帰と動的計画法は、同じ計算を別の順番でやっているだけ
  • 誕生日のパラドックスは「めずらしい話」ではなく、ハッシュの衝突がなぜ早いかの答え

この記事でやること

  1. 実験用フォルダ ~/cslab/rec を作り、この記事の作業を全部そこに閉じ込める
  2. 再帰を2つの型として書き、階乗とフォルダ容量で確かめる
  3. 素朴なフィボナッチの呼び出し回数を数え、木に描いて「同じ引数」を目で見る
  4. メモ化を足して、fib(90) が 1ms 未満で返ることを実測する
  5. 末尾再帰を深く回してスタックを溢れさせ、ループに書き換えて溢れないことを確かめる
  6. N-Queen を書き、枝刈りあり・なしで調べた盤面の数を比べる
  7. ナイトの巡回で、順番を変えるだけで探索量が桁で変わることを実測する
  8. ナップサックを総当たり・メモ化再帰・動的計画法の3通りで書き、時間を並べる
  9. 順列・組み合わせを列挙し、誕生日のパラドックスをシミュレーションする

先に知る言葉

基本的な言葉は用語集にもまとめてあります。

言葉意味
再帰関数が自分自身を呼ぶこと。入れ子の構造を、入れ子のまま扱える
ベースケース再帰が止まる条件。これを書かないと止まらない。「終わり方を先に書く」
コールスタック「どこから呼ばれたか」を積んでおく場所。有限。積みすぎると溢れる
メモ化一度計算した結果を覚えておき、同じ引数なら計算し直さないこと
動的計画法小さい答えから順に表を埋めていくやり方。メモ化再帰の順番を逆にしたもの
バックトラック候補を1つ置いて先へ進み、だめなら置いたものを戻して次を試す探索
枝刈り「この先は絶対だめ」と分かった時点で引き返すこと。バックトラックの速さはここで決まる
末尾再帰自分を呼んだ結果をそのまま返す形の再帰。理屈上はループに書き換えられる
順列(nPr)n個からr個を選び、並べる。AB と BA を別に数える
組み合わせ(nCr)n個からr個を選ぶ。並び順は区別しない。AB と BA は同じ

① 再帰の書き方は2つしかない

作業場所を作ります。VMの中(Ubuntu Server)で打ちます。

bash
$ mkdir -p ~/cslab/rec
$ cd ~/cslab/rec
$ node --version
v22.14.0

Node.js が入っていない場合は先に入れます。

bash
$ sudo apt update
$ sudo apt install -y nodejs

再帰は「難しい考え方」ではなく、2つの型

再帰を難しく感じていた理由は、頭の中で全部の呼び出しを追おうとしていたからでした。追う必要はありません。書くのは次の2つだけです。

1. 終わる条件(ベースケース)を先に書く
2. 1段だけ小さくして、自分を呼ぶ

「1段小さくしたやつは、もう正しく動く」と信じて書く。 これが全部です。

階乗で書いてみます。

bash
$ cat > basic.mjs <<'EOF'
  function fact(n) {
    if (n <= 1) return 1;        // 1. 終わる条件
    return n * fact(n - 1);      // 2. 1段小さくして自分を呼ぶ
  }
  console.log('fact(5)  =', fact(5));
  console.log('fact(20) =', fact(20));
  console.log('fact(21) =', fact(21));
  EOF
$ node basic.mjs
fact(5)  = 120
fact(20) = 2432902008176640000
fact(21) = 51090942171709440000

fact(5) が 120。合っています。

fact(21) は、もう正しさが保証されない範囲に入っています。 Number がどの整数でも正確に表せるのは 9007199254740991 までで、fact(21) はそれを超えています(fact(21) と fact(22) はたまたま正確で、実際にずれ始めるのは fact(23) からです)。エラーは出ません。静かにずれます。 これは②でもう一度出てきます。

フォルダの容量を数える — 再帰が本当に効く形

階乗は正直、ループで書いたほうが簡単です。再帰が本当に効くのは、データそのものが入れ子になっているときです。フォルダはその代表です。

bash
$ cat > dirsize.mjs <<'EOF'
  import { readdir, stat } from 'node:fs/promises';
  import { join } from 'node:path';
  
  async function dirSize(path) {
    let total = 0;
    for (const e of await readdir(path, { withFileTypes: true })) {
      const p = join(path, e.name);
      if (e.isDirectory()) {
        total += await dirSize(p);   // 中身も同じ関数で数える
      } else if (e.isFile()) {
        total += (await stat(p)).size;
      }
    }
    return total;   // 終わる条件 = 「中身が無ければループが回らず 0 で返る」
  }
  
  console.log('合計 =', await dirSize(process.argv[2] ?? '.'), 'バイト');
  EOF
$ node dirsize.mjs ~/cslab
合計 = 11693 バイト

ここでのベースケースは if で書いていません。「中に何も無ければ for が1回も回らず、0 を返して終わる」が終わる条件です。再帰の終わりは、必ずしも if の形をしていません。

フォルダの中にフォルダがある構造を、ループで書こうとすると、自分でスタックを用意することになります。 入れ子の構造は、入れ子のまま書けるほうが読めます。 これが再帰を使う一番の理由です。

終わる条件を忘れると何が起きるか

わざと忘れます。

bash
$ cat > nostop.mjs <<'EOF'
  function countdown(n) {
    console.log(n);
    countdown(n - 1);   // 終わる条件が無い
  }
  countdown(3);
  EOF
$ node nostop.mjs 2>&1 | tail -6
    at countdown (file:///home/user/cslab/rec/nostop.mjs:3:3)
    at countdown (file:///home/user/cslab/rec/nostop.mjs:3:3)
    at countdown (file:///home/user/cslab/rec/nostop.mjs:3:3)

Node.js v22.14.0

いちばん上に出るのは RangeError: Maximum call stack size exceeded です。前の回(call stack size exceeded の正体)で見たものと同じです。

無限ループなら固まるだけですが、無限再帰は落ちます。 呼び出しごとに「戻り先」をスタックに積むので、メモリが先に尽きるからです。落ちてくれるのは、むしろ親切です。

どのくらい積めるのか数えます。

bash
$ cat > depth.mjs <<'EOF'
  let depth = 0;
  function probe() { depth++; probe(); }
  try { probe(); } catch (e) { console.log('限界の深さ =', depth, '/', e.message); }
  EOF
$ node depth.mjs
限界の深さ = 12529 / Maximum call stack size exceeded

約12,500段。 万単位の深さになる再帰は、それだけで危険だと分かります。③で戻ってきます。

📸 スクリーンショット①: node nostop.mjs を打って RangeError: Maximum call stack size exceeded が出ている画面と、node depth.mjs の「限界の深さ」の行。エラーが「バグ」ではなく「積みすぎ」だと分かる並びにする。


② 同じ計算を何度もしている

ここがこの記事の中心です。

まず、遅さを測る

bash
$ cat > fib.mjs <<'EOF'
  function fib(n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
  }
  for (const n of [30, 35, 40]) {
    const t = performance.now();
    const v = fib(n);
    console.log(`fib(${n}) = ${v}   ${(performance.now() - t).toFixed(1)} ms`);
  }
  EOF
$ node fib.mjs
fib(30) = 832040   15.9 ms
fib(35) = 9227465   160.1 ms
fib(40) = 102334155   2133.4 ms
n時間前の行の何倍か
3015.9 ms—
35160.1 ms10.1倍
402133.4 ms13.3倍

n を5足すたびに11倍前後。 n を1足すごとに約1.6倍です。これは O(2^n) に近い、指数的な伸び方です。

「データが10倍で100倍」だった O(n²) ですら、これに比べれば穏やかです(データが10倍で100倍遅くなる)。指数はグラフの形が違います。

何回呼ばれているのかを数える

推測ではなく、数えます。カウンタを1個足すだけです。

bash
$ cat > fibcount.mjs <<'EOF'
  let calls = 0;
  function fib(n) {
    calls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
  }
  for (const n of [10, 20, 30, 35]) {
    calls = 0;
    fib(n);
    console.log(`fib(${n}) 呼び出し回数 = ${calls.toLocaleString()}`);
  }
  EOF
$ node fibcount.mjs
fib(10) 呼び出し回数 = 177
fib(20) 呼び出し回数 = 21,891
fib(30) 呼び出し回数 = 2,692,537
fib(35) 呼び出し回数 = 29,860,703

fib(35) を出すのに、関数が 2,986万回 呼ばれています。

答えは35個の数字を足せば出るはずです。なぜ3000万回も呼ぶのか。

呼び出しの木を描いて、目で見る

fib(5) の呼び出しを、そのまま字下げで出してみます。

bash
$ cat > tree.mjs <<'EOF'
  function tree(n, depth = 0, out = []) {
    out.push('  '.repeat(depth) + `fib(${n})`);
    if (n >= 2) { tree(n - 1, depth + 1, out); tree(n - 2, depth + 1, out); }
    return out;
  }
  console.log(tree(5).join('\n'));
  EOF
$ node tree.mjs
fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)

数えてみます。

引数出てくる回数
fib(3)2回
fib(2)3回
fib(1)5回
fib(0)3回

fib(2) を3回、fib(1) を5回、それぞれ最初から計算し直しています。

n = 5 でこれです。n = 35 なら、fib(2) は数百万回計算されます。答えは毎回同じなのに。

これが「素朴な再帰が遅い」の正体です。再帰が遅いのではありません。同じ問いを何度も聞いているのが遅いのです。

メモ化 — 覚えさせる

一度出した答えを Map に入れて、次からはそれを返します。足すのは実質3行です。

bash
$ cat > memo.mjs <<'EOF'
  let calls = 0;
  function fibMemo(n, memo = new Map()) {
    calls++;
    if (n < 2) return n;
    if (memo.has(n)) return memo.get(n);      // ← 覚えていたら返す
    const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, v);                           // ← 覚える
    return v;
  }
  for (const n of [35, 40, 90]) {
    calls = 0;
    const t = performance.now();
    const v = fibMemo(n);
    console.log(`fib(${n}) = ${v}  ${(performance.now() - t).toFixed(3)} ms  呼び出し ${calls} 回`);
  }
  EOF
$ node memo.mjs
fib(35) = 9227465  0.117 ms  呼び出し 69 回
fib(40) = 102334155  0.073 ms  呼び出し 79 回
fib(90) = 2880067194370816000  0.043 ms  呼び出し 179 回

並べます。

n素朴な再帰メモ化呼び出し回数(素朴 → メモ化)
35160.1 ms0.117 ms29,860,703 → 69
402133.4 ms0.073 ms約3億3千万 → 79
90(終わらない)0.043 ms— → 179

fib(40) が 2133ms から 0.073ms。約29,000倍です。 アルゴリズムは1文字も変えていません。同じ引数を2回計算しないようにしただけです。

呼び出し回数の 179 に注目します。n = 90 で 179 = 2 × 90 - 1。呼び出し回数が n に正比例しています。O(2^n) が O(n) になりました。

ただし fib(90) の値は間違っている

出力をよく見ます。

fib(90) = 2880067194370816000

末尾が 000 です。怪しい。Number の安全整数の上限を超えています。

bash
$ cat > big.mjs <<'EOF'
  console.log('Number.MAX_SAFE_INTEGER =', Number.MAX_SAFE_INTEGER);
  function fibBig(n, memo = new Map()) {
    if (n < 2) return BigInt(n);
    if (memo.has(n)) return memo.get(n);
    const v = fibBig(n - 1, memo) + fibBig(n - 2, memo);
    memo.set(n, v);
    return v;
  }
  console.log('BigInt fib(90)  =', fibBig(90).toString());
  console.log('BigInt fib(200) =', fibBig(200).toString());
  EOF
$ node big.mjs
Number.MAX_SAFE_INTEGER = 9007199254740991
BigInt fib(90)  = 2880067194370816120
BigInt fib(200) = 280571172992510140037611932413038677189525
型fib(90)
Number2880067194370816000
BigInt2880067194370816120

下3桁が違います。 そして例外も警告も出ません。

これは 0.1+0.2が0.3にならない と同じ根っこです。Number は64bitの浮動小数点なので、大きい整数は途中から飛び飛びになります。

「速くした」と「正しくなった」は別の話です。 fib(90) を 0.04ms で出せても、値が違えば意味がありません。BigInt が要ります。

BigInt にするときの注意は2つです。

  • リテラルの末尾に n を付ける(0n、1n)か、BigInt(n) で作る
  • Number と BigInt は + で混ぜられない。 Cannot mix BigInt and other types になる

📸 スクリーンショット②: node fib.mjs(2133ms)と node memo.mjs(0.073ms)を続けて打った画面。同じ端末に並べて撮る。


③ 末尾再帰は、JavaScript では救いにならない

末尾再帰とは何か

「自分を呼んだ結果を、そのまま返す」形の再帰です。

// 末尾再帰ではない:呼んだあとに n を掛ける仕事が残っている
function fact(n) { return n * fact(n - 1); }

// 末尾再帰:呼んだ結果をそのまま返している
function factTail(n, acc = 1) { return n <= 1 ? acc : factTail(n - 1, acc * n); }

違いは、呼んだあとに仕事が残っているかどうかです。残っていなければ、呼び出し元のスタックの枠はもう要りません。理屈上は、そのまま使い回してループと同じにできます。これを末尾呼び出し最適化と呼びます。

ECMAScript の仕様には、これは入っています。 では効くのか、試します。

bash
$ cat > tail.mjs <<'EOF'
  function sumTail(n, acc = 0) {
    if (n === 0) return acc;
    return sumTail(n - 1, acc + n);   // 完全な末尾呼び出し
  }
  for (const n of [1000, 10000, 100000]) {
    try { console.log(`sumTail(${n}) = ${sumTail(n)}`); }
    catch (e) { console.log(`sumTail(${n}) → ${e.constructor.name}: ${e.message}`); }
  }
  EOF
$ node tail.mjs
sumTail(1000) = 500500
sumTail(10000) → RangeError: Maximum call stack size exceeded
sumTail(100000) → RangeError: Maximum call stack size exceeded

完全な末尾再帰なのに、10,000段で溢れました。

理由は身も蓋もありません。V8(Chrome と Node.js のエンジン)は末尾呼び出し最適化を実装していません。 仕様には書かれていますが、実装しているのは事実上 Safari の JavaScriptCore だけです。

「末尾再帰に書き直したから深くても大丈夫」は、JavaScript では成立しません。 私はここを「仕様にあるなら効くはず」と思い込んでいました。測るまで分かりませんでした。

ではどうするか — 自分でループにする

末尾再帰は、機械的にループへ書き換えられます。 引数が変数に、再帰呼び出しが代入になるだけです。

bash
$ cat > loop.mjs <<'EOF'
  function sumLoop(n) {
    let acc = 0;
    for (let i = n; i > 0; i--) acc += i;
    return acc;
  }
  console.log('sumLoop(100000)   =', sumLoop(100000));
  console.log('sumLoop(10000000) =', sumLoop(10000000));
  EOF
$ node loop.mjs
sumLoop(100000)   = 5000050000
sumLoop(10000000) = 50000005000000

1000万段でも平気です。 スタックを使っていないので、深さの上限がありません。

深い再帰をどう避けるか(3つ)

状況対処
単純な繰り返し(1回の呼び出しで1回だけ自分を呼ぶ)ループに書き換える。 ほぼ機械的にできる
木やフォルダを辿る(枝分かれする)そのまま再帰でよい。深さは対数的にしか増えない
リストを1万件以上、再帰で辿っている設計が間違っている。 スタックを配列で自作するか、ループにする

枝分かれする再帰の深さは、要素数ではなく「木の高さ」です。 100万件の平衡木でも深さは20です(100万件が3段で届く)。怖いのは「一直線に深くなる再帰」だけです。


④ バックトラック — 置く、進む、戻す

ここから、再帰が本当に強い領域に入ります。

型は3行

1. 候補を1つ置く
2. その状態で1段先へ進む(自分を呼ぶ)
3. 戻ってきたら、置いたものを戻して、次の候補を試す

3の「戻す」を書き忘れるのが最大の事故です。置きっぱなしのまま次を試すと、盤面が汚れたまま探索が続きます。

N-Queen を書く

N × N の盤に N個のクイーンを、互いに取り合わないように置きます。クイーンは縦・横・斜めに走ります。

「1行に1個ずつ置く」と決めると、確かめるのは列と2種類の斜めだけです。斜めは 行 - 列 と 行 + 列 が一致するかで判定できます。

bash
$ cat > queens.mjs <<'EOF'
  function solveN(n) {
    let nodes = 0, solutions = 0;
    const cols = new Set(), d1 = new Set(), d2 = new Set();
    function place(r) {
      nodes++;                                 // 調べた盤面を数える
      if (r === n) { solutions++; return; }    // 終わる条件:全部の行に置けた
      for (let c = 0; c < n; c++) {
        if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;   // ← 枝刈り
        cols.add(c); d1.add(r - c); d2.add(r + c);            // 1. 置く
        place(r + 1);                                          // 2. 進む
        cols.delete(c); d1.delete(r - c); d2.delete(r + c);   // 3. 戻す
      }
    }
    place(0);
    return { nodes, solutions };
  }
  for (let n = 4; n <= 8; n++) {
    const a = solveN(n);
    console.log(`N=${n}  解 ${a.solutions}  調べた盤面 ${a.nodes.toLocaleString()}`);
  }
  EOF
$ node queens.mjs
N=4  解 2  調べた盤面 17
N=5  解 10  調べた盤面 54
N=6  解 4  調べた盤面 153
N=7  解 40  調べた盤面 552
N=8  解 92  調べた盤面 2,057

N=8 の解は92通り。 よく知られた答えと一致しました。

8×8 の解の1つは、こういう並びです(Q がクイーン)。

Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

枝刈りが全部だと、数で確かめる

「置けないと分かった時点で戻る」をやめて、全部置いてから最後に検査する版を書きます。

bash
$ cat > naive-queens.mjs <<'EOF'
  function solveNaive(n) {
    let nodes = 0, solutions = 0;
    const pos = [];
    function ok() {
      for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) {
        if (pos[i] === pos[j]) return false;
        if (Math.abs(pos[i] - pos[j]) === j - i) return false;
      }
      return true;
    }
    function place(r) {
      nodes++;
      if (r === n) { if (ok()) solutions++; return; }   // 最後にまとめて検査
      for (let c = 0; c < n; c++) { pos[r] = c; place(r + 1); }
    }
    place(0);
    return { nodes, solutions };
  }
  for (let n = 4; n <= 8; n++) {
    const b = solveNaive(n);
    console.log(`N=${n}  解 ${b.solutions}  調べた盤面 ${b.nodes.toLocaleString()}`);
  }
  EOF
$ node naive-queens.mjs
N=4  解 2  調べた盤面 341
N=5  解 10  調べた盤面 3,906
N=6  解 4  調べた盤面 55,987
N=7  解 40  調べた盤面 960,800
N=8  解 92  調べた盤面 19,173,961

並べます。解の数は当然同じです。違うのは調べた量だけです。

N枝刈りあり枝刈りなし何倍解の数
41734120倍2
5543,90672倍10
615355,987366倍4
7552960,8001,741倍40
82,05719,173,9619,321倍92

N=8 で 9,321倍。 そしてこの差は N が増えるほど開きます。

枝刈りなしは 8^8 = 1677万 通りの並べ方を全部作っています。枝刈りありは、「この列はもう埋まっている」と分かった瞬間に、その先の枝ごと捨てています。

バックトラックの速さは、探索の書き方ではなく「どれだけ早く諦めるか」で決まります。

N を伸ばすと、どこで壁に当たるか

bash
$ cat > queens-scale.mjs <<'EOF'
  function solveN(n) {
    let nodes = 0, solutions = 0;
    const cols = new Set(), d1 = new Set(), d2 = new Set();
    function place(r) {
      nodes++;
      if (r === n) { solutions++; return; }
      for (let c = 0; c < n; c++) {
        if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;
        cols.add(c); d1.add(r - c); d2.add(r + c);
        place(r + 1);
        cols.delete(c); d1.delete(r - c); d2.delete(r + c);
      }
    }
    place(0);
    return { nodes, solutions };
  }
  for (let n = 8; n <= 13; n++) {
    const t = performance.now();
    const a = solveN(n);
    console.log(`N=${n}  解 ${a.solutions}  調べた盤面 ${a.nodes.toLocaleString()}  ${(performance.now() - t).toFixed(1)} ms`);
  }
  EOF
$ node queens-scale.mjs
N=8  解 92  調べた盤面 2,057  1.7 ms
N=9  解 352  調べた盤面 8,394  10.5 ms
N=10  解 724  調べた盤面 35,539  27.0 ms
N=11  解 2680  調べた盤面 166,926  127.8 ms
N=12  解 14200  調べた盤面 856,189  687.9 ms
N=13  解 73712  調べた盤面 4,674,890  4757.4 ms
N解の数調べた盤面時間前の行の何倍
8922,0571.7 ms—
93528,39410.5 ms6.2倍
1072435,53927.0 ms2.6倍
112,680166,926127.8 ms4.7倍
1214,200856,189687.9 ms5.4倍
1373,7124,674,8904757.4 ms6.9倍

N を1増やすごとに、5〜7倍。これも指数です。

枝刈りをしても、指数は指数のままです。 定数倍が9000分の1になっただけで、伸び方の形は変わりません。N=20 は、この延長では終わりません。

これが「全部の組み合わせを調べる問題」の性格です。②のメモ化のように O(n) に落ちる魔法は、ここにはありません。


⑤ ナイトの巡回 — 順番を変えるだけで桁が変わる

同じバックトラックで、もう1つ。チェスのナイト(将棋の桂馬に似た動き)で、盤の全マスをちょうど1回ずつ通る経路を探します。

bash
$ cat > knight.mjs <<'EOF'
  const MOVES = [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]];
  
  function tour(N, useWarnsdorff, sr = 0, sc = 0, limit = Infinity) {
    const b = Array.from({ length: N }, () => Array(N).fill(-1));
    let nodes = 0, aborted = false;
    const inside = (r, c) => r >= 0 && r < N && c >= 0 && c < N;
    const degree = (r, c) => {
      let d = 0;
      for (const [dr, dc] of MOVES) {
        const nr = r + dr, nc = c + dc;
        if (inside(nr, nc) && b[nr][nc] < 0) d++;
      }
      return d;
    };
    function go(r, c, step) {
      if (++nodes > limit) { aborted = true; return false; }
      b[r][c] = step;                              // 1. 置く
      if (step === N * N - 1) return true;         // 終わる条件:全マス踏んだ
      const cand = [];
      for (const [dr, dc] of MOVES) {
        const nr = r + dr, nc = c + dc;
        if (inside(nr, nc) && b[nr][nc] < 0) cand.push([nr, nc]);
      }
      if (useWarnsdorff) cand.sort((a, z) => degree(a[0], a[1]) - degree(z[0], z[1]));
      for (const [nr, nc] of cand) {               // 2. 進む
        if (go(nr, nc, step + 1)) return true;
        if (aborted) return false;
      }
      b[r][c] = -1;                                // 3. 戻す
      return false;
    }
    return { ok: go(sr, sc, 0), nodes, aborted, b };
  }
  
  const show = (b) => {
    const w = String(b.length * b.length).length;
    return b.map(row => row.map(v => String(v).padStart(w)).join(' ')).join('\n');
  };
  
  let t = performance.now();
  let r = tour(5, false);
  console.log(`5x5 素朴: ${r.ok ? '解けた' : '失敗'} 調べた手 ${r.nodes.toLocaleString()} ${(performance.now() - t).toFixed(1)} ms`);
  console.log(show(r.b));
  
  t = performance.now();
  r = tour(5, true);
  console.log(`5x5 ワーンスドルフ: ${r.ok ? '解けた' : '失敗'} 調べた手 ${r.nodes.toLocaleString()} ${(performance.now() - t).toFixed(1)} ms`);
  EOF
$ node knight.mjs
5x5 素朴: 解けた 調べた手 8,840 27.6 ms
 0 13 18  7 24
 5  8  1 12 17
14 19  6 23  2
 9  4 21 16 11
20 15 10  3 22
5x5 ワーンスドルフ: 解けた 調べた手 25 1.2 ms

5×5 は素朴でも解けます。 8,840手。数字の並びは訪問順で、0 から 24 まで飛び番なしに埋まっています。

8×8 で止まる

盤を大きくします。上限5000万手で打ち切るようにして測りました。

7x7 開始(0,0) 素朴: 解けた 7,151,179手 2.2s
7x7 開始(0,0) W規則: 解けた 49手 0.9ms
8x8 開始(0,0) 素朴: 解けた 8,250,733手 1.7s
8x8 開始(0,0) W規則: 解けた 64手 1.0ms
8x8 開始(1,0) 素朴: 打ち切り 50,000,001手 11.6s
8x8 開始(1,0) W規則: 解けた 64手 0.2ms
8x8 開始(3,3) 素朴: 打ち切り 50,000,001手 12.2s
8x8 開始(3,3) W規則: 解けた 64手 0.1ms
10x10 開始(0,0) 素朴: 打ち切り 50,000,001手 10.3s
10x10 開始(0,0) W規則: 解けた 100手 0.3ms

ここは正直に書きます。「8×8 は素朴だと終わらない」と思っていましたが、角(0,0)から始めたときだけは825万手で解けました。 角はそもそも行ける先が2つしかないので、迷いようがなかったのです。

1マスずらすと終わりません。 (1,0) からも (3,3) からも、5000万手で打ち切りました。

「うまくいった1回」で結論を出すと間違えます。 開始位置を変えるだけで壊れました。

ワーンスドルフの規則 — 順番を変えるだけ

足したのは sort の1行だけです。

if (useWarnsdorff) cand.sort((a, z) => degree(a[0], a[1]) - degree(z[0], z[1]));

「次に行ける先が少ないマスから先に試す」。 それだけです。

盤開始素朴ワーンスドルフ
5×5(0,0)8,840手 / 27.6ms25手 / 1.2ms
7×7(0,0)7,151,179手 / 2.2s49手 / 0.9ms
8×8(0,0)8,250,733手 / 1.7s64手 / 1.0ms
8×8(3,3)5000万手で打ち切り / 12.2s64手 / 0.1ms
10×10(0,0)5000万手で打ち切り / 10.3s100手 / 0.3ms

64手。8×8 は64マスなので、これは「一度も戻っていない」ということです。

8×8 の答えはこう出ました(訪問順)。

 0  3 56 19 40  5 42 21
33 18  1  4 57 20 39  6
 2 55 34 59 36 41 22 43
17 32 47 52 45 58  7 38
48 13 54 35 60 37 44 23
31 16 51 46 53 26 61  8
12 49 14 29 10 63 24 27
15 30 11 50 25 28  9 62

なぜ効くのか。行き先が少ないマスは、後回しにすると「誰も行けない孤島」になります。 孤島ができると、そこに辿り着くまで探索を進めてから失敗して、全部戻ってくることになります。先に潰しておけば、その失敗そのものが起きません。

探索の量は、アルゴリズムだけでなく「試す順番」で決まります。 同じバックトラックで、825万手が64手になりました。

これはヒューリスティック(経験にもとづく優先順位付け)と呼ばれるものです。正しさを保証するものではありません — ワーンスドルフの規則は大きい盤では失敗することがあります。「速いが、いつも当たるとは限らない」という道具です。

📸 スクリーンショット③: 8x8 開始(3,3) の行が2行並んでいる画面。「5000万手で打ち切り 12.2s」と「64手 0.1ms」が上下に並んでいるところを撮る。


⑥ ナップサック — 同じ問題を3通りで書く

重さの上限があるとき、価値の合計を最大にする選び方を求める問題です。旅行カバンに何を詰めるか、そのままです。

商品は毎回同じものにしたいので、擬似乱数を固定の種で作ります。

bash
$ cat > knap.mjs <<'EOF'
  function makeItems(n, seed = 12345) {
    let s = seed;
    const rnd = () => { s = (s * 1103515245 + 12345) & 0x7fffffff; return s / 0x7fffffff; };
    return Array.from({ length: n }, () => ({ w: 1 + Math.floor(rnd() * 50), v: 1 + Math.floor(rnd() * 100) }));
  }
  
  // (1) 総当たり:入れるか入れないかを全部試す
  function brute(it, cap) {
    let calls = 0;
    function go(i, rest) {
      calls++;
      if (i === it.length || rest === 0) return 0;
      let best = go(i + 1, rest);                       // 入れない
      if (it[i].w <= rest) best = Math.max(best, it[i].v + go(i + 1, rest - it[i].w));  // 入れる
      return best;
    }
    return { v: go(0, cap), calls };
  }
  
  // (2) メモ化再帰:(何番目, 残り容量) の組で覚える
  function memo(it, cap) {
    let calls = 0; const m = new Map();
    function go(i, rest) {
      calls++;
      if (i === it.length || rest === 0) return 0;
      const k = i * (cap + 1) + rest;                   // ← キーは数値1つに潰す
      if (m.has(k)) return m.get(k);
      let best = go(i + 1, rest);
      if (it[i].w <= rest) best = Math.max(best, it[i].v + go(i + 1, rest - it[i].w));
      m.set(k, best);
      return best;
    }
    return { v: go(0, cap), calls, cells: m.size };
  }
  
  // (3) 動的計画法:表を小さいほうから埋める
  function dp(it, cap) {
    let ops = 0;
    const t = new Int32Array(cap + 1);
    for (const { w, v } of it) for (let c = cap; c >= w; c--) {
      ops++; const x = t[c - w] + v; if (x > t[c]) t[c] = x;
    }
    return { v: t[cap], ops };
  }
  
  const CAP = 200;
  console.log('n | 総当たり | メモ化再帰 | 動的計画法 | 価値');
  for (const n of [10, 15, 20, 25, 28, 30]) {
    const it = makeItems(n);
    let t = performance.now(); const b = brute(it, CAP); const tb = performance.now() - t;
    t = performance.now(); const m = memo(it, CAP);      const tm = performance.now() - t;
    t = performance.now(); const d = dp(it, CAP);        const td = performance.now() - t;
    console.log(`${n} | ${tb.toFixed(1)}ms (${b.calls.toLocaleString()}回) | ${tm.toFixed(2)}ms (${m.calls.toLocaleString()}回/表${m.cells}マス) | ${td.toFixed(3)}ms (${d.ops.toLocaleString()}回) | ${b.v}/${m.v}/${d.v}`);
  }
  EOF
$ node knap.mjs
n | 総当たり | メモ化再帰 | 動的計画法 | 価値
10 | 0.6ms (1,826回) | 0.50ms (933回/表494マス) | 0.380ms (1,705回) | 535/535/535
15 | 2.9ms (32,571回) | 0.51ms (2,582回/表1378マス) | 0.251ms (2,586回) | 609/609/609
20 | 12.2ms (332,790回) | 1.41ms (4,296回/表2310マス) | 0.227ms (3,436回) | 647/647/647
25 | 27.8ms (1,963,966回) | 1.44ms (6,025回/表3250マス) | 0.259ms (4,285回) | 709/709/709
28 | 82.7ms (4,837,382回) | 0.72ms (7,066回/表3814マス) | 0.439ms (4,798回) | 709/709/709
30 | 204.1ms (9,336,151回) | 1.29ms (7,777回/表4190マス) | 9.235ms (5,157回) | 755/755/755

まず、3つとも答えが同じであることを確認します(535/535/535 のように、同じ値が3つ並んでいます)。総当たりが検算(オラクル)になっています。 前の回でやった手です。

n総当たりメモ化再帰動的計画法
100.6 ms0.50 ms0.38 ms
152.9 ms0.51 ms0.25 ms
2012.2 ms1.41 ms0.23 ms
2527.8 ms1.44 ms0.26 ms
30204.1 ms1.29 ms9.2 ms

総当たりの呼び出し回数を見ます。

n呼び出し回数
101,826
20332,790
251,963,966
309,336,151

5増えるごとにおよそ5〜6倍。 ②のフィボナッチと同じ形です。n = 60 は無理です。

メモ化の「表◯◯マス」に注目します。n = 30 で 4,190マス。930万回の呼び出しが、実は4,190通りしかない問いだったということです。

メモ化再帰と動的計画法は同じもの

2つを見比べます。

メモ化再帰動的計画法
方向大きいほうから始めて、必要になった小さい問いを解く小さいほうから順に全部埋める
覚え場所Map(必要になったマスだけ)配列(全マス)
呼ばれ方再帰。スタックを使うループ。スタックを使わない
無駄無い(要るマスしか計算しない)ある(使わないマスも埋める)

やっている計算は同じです。順番と、覚える入れ物が違うだけです。

「動的計画法」という名前が難しそうなだけで、中身は「メモ化再帰を、下から順に書き直したもの」です。私はここが繋がるまで、別々の技だと思っていました。

n を伸ばして、差が出る場所を見る

bash
$ cat >> knap.mjs <<'EOF'
  
  console.log('--- 総当たりを外して n を伸ばす ---');
  for (const n of [50, 200, 1000]) {
    const it = makeItems(n);
    let t = performance.now(); const m = memo(it, CAP); const tm = performance.now() - t;
    t = performance.now(); const d = dp(it, CAP);       const td = performance.now() - t;
    console.log(`n=${n} メモ化 ${tm.toFixed(1)}ms / 動的計画法 ${td.toFixed(2)}ms / 価値 ${m.v}=${d.v}`);
  }
  EOF
$ node knap.mjs | tail -4
--- 総当たりを外して n を伸ばす ---
n=50 メモ化 2.7ms / 動的計画法 0.07ms / 価値 1021=1021
n=200 メモ化 25.2ms / 動的計画法 0.15ms / 価値 2100=2100
n=1000 メモ化 226.0ms / 動的計画法 0.82ms / 価値 4655=4655
nメモ化再帰動的計画法差
502.7 ms0.07 ms39倍
20025.2 ms0.15 ms168倍
1000226.0 ms0.82 ms276倍

計算量は同じ O(n × 容量) なのに、実測で276倍開きました。差の中身は、

  • 再帰の呼び出しそのもののコスト(引数を積んで、戻る)
  • Map のハッシュ計算(10万件のincludesで止まる)
  • 動的計画法側は Int32Array を連番で舐めるのでキャッシュに乗る(前の回で見たキャッシュの話)

計算量が同じでも、定数倍で276倍違います。 ただし、まず動くのはメモ化再帰のほうです。素朴な再帰にメモを足すだけなので、間違えにくい。 メモ化再帰で正しさを作ってから、必要なら動的計画法に書き直す。 この順番が現実的です。


⑦ 組み合わせと確率 — なぜハッシュはすぐ衝突するのか

再帰で「全部の並べ方」を作る話に戻ります。ここが実は、確率の入口です。

順列と組み合わせを、実際に列挙する

bash
$ cat > comb.mjs <<'EOF'
  // 順列 nPr:並べる。使ったものに印を付けて、毎回ぜんぶ見に行く
  function permutations(arr, r) {
    const res = [], used = arr.map(() => false), cur = [];
    (function go() {
      if (cur.length === r) { res.push(cur.join('')); return; }
      for (let i = 0; i < arr.length; i++) {
        if (used[i]) continue;
        used[i] = true; cur.push(arr[i]);
        go();
        cur.pop(); used[i] = false;
      }
    })();
    return res;
  }
  
  // 組み合わせ nCr:選ぶ。「次はこの添字より後ろ」と決めれば重複しない
  function combinations(arr, r) {
    const res = [], cur = [];
    (function go(start) {
      if (cur.length === r) { res.push(cur.join('')); return; }
      for (let i = start; i < arr.length; i++) {
        cur.push(arr[i]);
        go(i + 1);
        cur.pop();
      }
    })(0);
    return res;
  }
  
  const a = ['A', 'B', 'C', 'D'];
  const P = permutations(a, 2), C = combinations(a, 2);
  console.log('nPr (4P2) =', P.length, ':', P.join(' '));
  console.log('nCr (4C2) =', C.length, ':', C.join(' '));
  console.log('4P3 =', permutations(a, 3).length, ' 4C3 =', combinations(a, 3).length);
  EOF
$ node comb.mjs
nPr (4P2) = 12 : AB AC AD BA BC BD CA CB CD DA DB DC
nCr (4C2) = 6 : AB AC AD BC BD CD
4P3 = 24  4C3 = 4

目で見ると一発です。

  • 順列には AB と BA が両方あります → 12通り
  • 組み合わせには AB しかありません → 6通り
  • 12 ÷ 6 = 2。これは「2個の並べ方 = 2通り」で割った数です

コードの違いも1箇所だけです。

順列組み合わせ
ループの始まりi = 0(毎回全部見る)i = start(自分より後ろだけ)
使用済みの管理used[] が要る要らない

「start より後ろしか見ない」と決めるだけで、並び順の重複が消えます。 これはバックトラックで重複を潰すときの定番の型です。

誕生日のパラドックス — 実際に回して数える

「23人集まれば、同じ誕生日の人がいる確率が50%を超える」。 直感に反します。365日あるのに。

信じずに、20万回シミュレーションします。

bash
$ cat > birthday.mjs <<'EOF'
  function trial(k) {
    const seen = new Set();
    for (let i = 0; i < k; i++) {
      const d = Math.floor(Math.random() * 365);
      if (seen.has(d)) return true;
      seen.add(d);
    }
    return false;
  }
  function sim(k, T = 200000) { let hit = 0; for (let i = 0; i < T; i++) if (trial(k)) hit++; return hit / T; }
  function theory(k) { let p = 1; for (let i = 0; i < k; i++) p *= (365 - i) / 365; return 1 - p; }
  
  console.log('人数 | 実測(20万回) | 理論値');
  for (const k of [5, 10, 20, 22, 23, 24, 30, 40, 50, 60, 70])
    console.log(`${k} | ${(sim(k) * 100).toFixed(1)}% | ${(theory(k) * 100).toFixed(1)}%`);
  EOF
$ node birthday.mjs
人数 | 実測(20万回) | 理論値
5 | 2.7% | 2.7%
10 | 11.8% | 11.7%
20 | 41.2% | 41.1%
22 | 47.6% | 47.6%
23 | 50.7% | 50.7%
24 | 53.9% | 53.8%
30 | 70.7% | 70.6%
40 | 89.1% | 89.1%
50 | 97.1% | 97.0%
60 | 99.4% | 99.4%
70 | 99.9% | 99.9%
人数実測理論
2247.6%47.6%
2350.7%50.7%
2453.9%53.8%
5097.1%97.0%

23人でちょうど50%を超えました。実測と理論が小数点1桁まで一致しています。

なぜ少ない人数で当たるのか。数えているのが「人数」ではなく「ペアの数」だからです。23人のペアは 23C2 = 253組。253回くじを引いているのと同じです。それなら 365 に対して半々になるのも分かります。

組み合わせの数え方(⑦の前半)が、そのまま確率の答えになっています。

これがハッシュの衝突が早い理由

前の回(10万件のincludesで止まる)で、ハッシュテーブルの衝突を見ました。「枠がたくさんあるのになぜ当たるのか」の答えが、これです。

bash
$ cat > collide.mjs <<'EOF'
  function collideAt(buckets) {
    const seen = new Set();
    let n = 0;
    for (;;) { n++; const h = Math.floor(Math.random() * buckets); if (seen.has(h)) return n; seen.add(h); }
  }
  for (const b of [1000, 1000000, 4294967296]) {
    let s = 0;
    for (let i = 0; i < 2000; i++) s += collideAt(b);
    console.log(`枠 ${b.toLocaleString()} 個 → 平均 ${Math.round(s / 2000).toLocaleString()} 個目で衝突(√枠数 = ${Math.round(Math.sqrt(b)).toLocaleString()})`);
  }
  EOF
$ node collide.mjs
枠 1,000 個 → 平均 41 個目で衝突(√枠数 = 32)
枠 1,000,000 個 → 平均 1,254 個目で衝突(√枠数 = 1,000)
枠 4,294,967,296 個 → 平均 79,907 個目で衝突(√枠数 = 65,536)
枠の数平均で何個目に衝突するか√枠数
1,0004132
1,000,0001,2541,000
約43億(32bit)79,90765,536

「枠の数の平方根くらい」で衝突します。

32bit のハッシュ値は約43億通りありますが、8万個入れただけで衝突します。 「43億分の1だから当たらない」は間違いです。当たるのは「値とハッシュ値」ではなく「値どうし」なので、ペアの数で効いてきます。

だからハッシュテーブルには最初から衝突処理が入っています。 「めったに起きないから無視」ではなく、必ず起きる前提で作られています。


⑧ 判断表 — どれを使うか

ここまでの道具を、選ぶ順に並べます。

再帰にすべきか、ループにすべきか

状況どちら理由
木・グラフ・フォルダなど入れ子の構造を辿る再帰構造と書き方が一致する。ループだと自分でスタックを持つことになる
JSON やコメント欄など深さが決まっていない入れ子再帰同上。ただし深さの上限は決めておく
配列を頭から順に処理するループ再帰にしても読みにくくなるだけ
1万件以上を1段ずつ辿る(連結リストなど)ループ12,500段で Maximum call stack size exceeded
末尾再帰だから深くても大丈夫だと思っているループV8 に末尾呼び出し最適化は無い。溢れる

メモ化を足すとき

兆候対処
同じ引数で何度も呼ばれている(カウンタを入れると分かる)メモ化する。 これが最大の効き目
引数の組み合わせの総数が、呼び出し回数よりずっと少ないメモ化する。 ナップサックは930万回 → 4,190マス
引数が毎回違う(探索・入出力)メモ化しても効かない。 覚える意味がない
副作用がある関数(DBを書く、ファイルを消す)メモ化してはいけない。 2回目が実行されなくなる
メモが際限なく増える危険。 上限や有効期限を決める。長時間動くサーバーではメモリリークになる

バックトラックにするとき

状況どうするか
全部の組み合わせから、条件を満たすものを探すバックトラック。N-Queen・数独・迷路
候補が明らかに少ない(数千通り以下)総当たりでよい。 早く書けて間違えにくい
途中で「もうだめ」と分かるバックトラック。枝刈りが命。9,321倍違った
途中では判定できず、最後まで作らないと分からないバックトラックにしても効かない。総当たりと同じ
最適解が要る(最大・最小)まずメモ化再帰。 それでも遅ければ動的計画法
部分問題が繰り返し出てくる動的計画法。ナップサック・最短経路

迷ったときの順番

1. まず素朴に書く(総当たり・素朴な再帰)— 正しさを作る
2. 遅かったら、呼び出し回数をカウンタで数える  ← ここを飛ばさない
3. 同じ引数が再登場していたら → メモ化を足す
4. 早く諦められる条件があるなら → 枝刈りを足す
5. 探す順番に意味がありそうなら → 並べ替えを足す(ワーンスドルフ)
6. それでも足りなければ → 動的計画法に書き直す
7. 素朴版は消さない。検算に使う

2 を飛ばして 6 から始めると、直す場所を間違えます。 私は最初「フィボナッチが遅いのは再帰だから」と思って、ループに書き換えようとしていました。原因は再帰ではなく再計算でした。


つまずいたところ

1. 「無限ループだ」と思って n の減り方を疑った

fib(45) が返ってこないとき、最初に n - 1 と n - 2 が本当に減っているか確かめました。減っていました。 論理は正しくて、ただ回数が多すぎるだけでした。 止まらないコードには2種類あります。「止まらない」と「終わらない」。 後者は n を小さくすると必ず返ってくるので、そこで見分けられます。

2. fib(90) が速く返って喜んだが、値が間違っていた

0.043 ms という数字だけ見て満足しました。末尾の 000 に気づいたのは、あとから BigInt 版と並べたときです。 Number の安全整数は 9007199254740991。超えても例外は出ません。 速度を測るときは、必ず答えの正しさも一緒に確かめること。

3. 末尾再帰にすれば深くても大丈夫だと思っていた

ECMAScript の仕様に末尾呼び出し最適化が入っていると読んで、sumTail(100000) を書きました。10,000段で落ちました。 V8 は実装していません。 仕様にあることと、使っている処理系が実装していることは別です。「仕様にあるから」で判断せず、走らせて確かめる。

4. N-Queen で「戻す」を書き忘れた

cols.add(c) は書いたのに cols.delete(c) を忘れて、N=8 の解が 0 になりました。エラーは出ません。1行目で置いた列がずっと埋まったままなので、2行目以降どこにも置けなくなっていただけです。 バックトラックのバグは「解が0通り」か「解が多すぎる」で出ます。 既知の答え(N=8 は92通り)と突き合わせないと気づけません。

5. ナイトの巡回が「8×8 で解けた」ので、解けると思い込んだ

角 (0,0) から始めたら825万手で解けました。開始位置を (3,3) に変えたら、5000万手で打ち切りになりました。 1つの入力で成功しても、それは「たまたま」かもしれません。 角は行ける先が2つしかないので、迷いようがなかっただけでした。入力を変えて測り直す。

6. 動的計画法が n=30 だけ 9.2ms と遅かった

表を見ると n=25 が 0.26ms、n=30 が 9.2ms、n=50 が 0.07ms です。n=30 だけ跳ねています。 これは JIT の最適化やガベージコレクションが挟まったせいで、アルゴリズムのせいではありません。 1回だけの計測は跳ねます。 本当は同じ処理を何度も回して中央値を取るべきでした。「1回測って遅いから遅い」と結論を出さない。

7. メモ化のキーを [i, rest] の配列にして効かなかった

最初 m.set([i, rest], best) と書きました。1回もヒットしませんでした。 Map のキーが配列だと、参照で比較されます。 中身が同じ [3, 50] を2回作っても、別のオブジェクトなので一致しません。i * (cap + 1) + rest のように1つの数値に潰すか、文字列にします。

8. メモを関数の外の変数に置いて、2回目から答えが壊れた

const memo = new Map() をモジュールの一番外に書いたら、別の商品リストで呼んだときに前回の答えが返ってきました。 メモの寿命を決めていないのが原因です。 引数の既定値 memo = new Map() にすると、呼び出しごとに新しくなります。キャッシュは「いつ消えるか」を先に決める。


後片づけ

この記事で作ったものは全部 ~/cslab/rec の中です。そのまま消せます。

bash
$ ls ~/cslab/rec
basic.mjs   big.mjs      birthday.mjs      collide.mjs   comb.mjs
depth.mjs   dirsize.mjs  fib.mjs           fibcount.mjs  knap.mjs
knight.mjs  loop.mjs     memo.mjs          naive-queens.mjs
nostop.mjs  queens.mjs   queens-scale.mjs  tail.mjs      tree.mjs
bash
$ cd ~
$ rm -rf ~/cslab/rec
$ ls ~/cslab

インストールしたものはありません(Node.js だけを使いました)。~/cslab ごと消しても構いません。

bash
$ rm -rf ~/cslab

まとめ — 理解できたこと

  • 再帰に書くのは2つだけ。 「終わる条件」と「1段小さくして自分を呼ぶ」。全部の呼び出しを頭で追う必要は無い
  • 終わる条件は if とは限らない。 フォルダ容量の例は「中身が無ければループが回らない」が終わり方だった
  • 終わる条件を忘れると Maximum call stack size exceeded。 無限ループは固まるが、無限再帰は落ちる
  • 積める深さは実測で約12,500段。 万単位の深さになる再帰は、それだけで危険
  • 素朴な再帰が遅い原因は、ほぼ「同じ引数の再計算」。 fib(35) は 29,860,703回呼ばれていた
  • 呼び出しの木を描くと、fib(5) ですら fib(1) を5回計算しているのが目で見える
  • メモ化は実質3行。 fib(40) が 2133ms → 0.073ms(約29,000倍)、呼び出し回数は n に正比例まで落ちた
  • 速くなっても正しいとは限らない。 fib(90) は Number では末尾3桁が違う。BigInt が要る
  • JavaScript に末尾呼び出し最適化は無い。 仕様にはあるが V8 は実装しておらず、完全な末尾再帰が10,000段で溢れた。深い再帰は自分でループに直す
  • バックトラックは「置く → 進む → 戻す」の3行。 「戻す」を忘れると解が0通りになる
  • 枝刈りが全部。 N=8 の N-Queen で 2,057盤面 対 19,173,961盤面(9,321倍)。解の数はどちらも92通り
  • 枝刈りをしても指数は指数のまま。 N を1増やすごとに5〜7倍。定数倍が9000分の1になっただけ
  • 探す順番を変えるだけで桁が変わる。 ワーンスドルフの規則で 8×8 のナイトの巡回が 825万手 → 64手(64マスなので一度も戻っていない)
  • 1つの入力で成功しても結論にしない。 8×8 は角から始めたときだけ解けて、(3,3) からは打ち切りだった
  • メモ化再帰と動的計画法は同じ計算。 順番(上から / 下から)と入れ物(Map / 配列)が違うだけ
  • 計算量が同じでも定数倍で276倍違う(n=1000 のナップサック)。ただし先に書くべきはメモ化再帰。正しさを作ってから書き直す
  • 総当たりは検算に使う。 ナップサックで3つの答えが一致したことが、実装が正しい根拠になった
  • 順列と組み合わせの差は、ループの始まりが 0 か start かだけ。 4P2 = 12、4C2 = 6
  • 誕生日のパラドックスは実測でも23人で50.7%。 数えているのは人数ではなくペアの数(23C2 = 253組)
  • ハッシュの衝突は「枠の数の平方根」で起きる。 32bit(約43億枠)でも8万個で衝突。だから衝突処理は必須で、「めったに起きない」ではない

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 15 / 25 本目です。

記事
← 前の記事最短経路アルゴリズム — ダイクストラは負の重みで壊れる
→ 次の記事文字列探索とKMP — grepは1文字ずつ見ていない

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Recursion & Backtracking
  • メモ化で指数が線形になる
  • 枝刈りで探索量が桁で変わる

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次