メモを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手)
- メモ化再帰と動的計画法は、同じ計算を別の順番でやっているだけ
- 誕生日のパラドックスは「めずらしい話」ではなく、ハッシュの衝突がなぜ早いかの答え
この記事でやること
- 実験用フォルダ
~/cslab/recを作り、この記事の作業を全部そこに閉じ込める - 再帰を2つの型として書き、階乗とフォルダ容量で確かめる
- 素朴なフィボナッチの呼び出し回数を数え、木に描いて「同じ引数」を目で見る
- メモ化を足して、
fib(90)が 1ms 未満で返ることを実測する - 末尾再帰を深く回してスタックを溢れさせ、ループに書き換えて溢れないことを確かめる
- N-Queen を書き、枝刈りあり・なしで調べた盤面の数を比べる
- ナイトの巡回で、順番を変えるだけで探索量が桁で変わることを実測する
- ナップサックを総当たり・メモ化再帰・動的計画法の3通りで書き、時間を並べる
- 順列・組み合わせを列挙し、誕生日のパラドックスをシミュレーションする
先に知る言葉
基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 再帰 | 関数が自分自身を呼ぶこと。入れ子の構造を、入れ子のまま扱える |
| ベースケース | 再帰が止まる条件。これを書かないと止まらない。「終わり方を先に書く」 |
| コールスタック | 「どこから呼ばれたか」を積んでおく場所。有限。積みすぎると溢れる |
| メモ化 | 一度計算した結果を覚えておき、同じ引数なら計算し直さないこと |
| 動的計画法 | 小さい答えから順に表を埋めていくやり方。メモ化再帰の順番を逆にしたもの |
| バックトラック | 候補を1つ置いて先へ進み、だめなら置いたものを戻して次を試す探索 |
| 枝刈り | 「この先は絶対だめ」と分かった時点で引き返すこと。バックトラックの速さはここで決まる |
| 末尾再帰 | 自分を呼んだ結果をそのまま返す形の再帰。理屈上はループに書き換えられる |
| 順列(nPr) | n個からr個を選び、並べる。AB と BA を別に数える |
| 組み合わせ(nCr) | n個からr個を選ぶ。並び順は区別しない。AB と BA は同じ |
① 再帰の書き方は2つしかない
作業場所を作ります。VMの中(Ubuntu Server)で打ちます。
v22.14.0
Node.js が入っていない場合は先に入れます。
再帰は「難しい考え方」ではなく、2つの型
再帰を難しく感じていた理由は、頭の中で全部の呼び出しを追おうとしていたからでした。追う必要はありません。書くのは次の2つだけです。
1. 終わる条件(ベースケース)を先に書く
2. 1段だけ小さくして、自分を呼ぶ
「1段小さくしたやつは、もう正しく動く」と信じて書く。 これが全部です。
階乗で書いてみます。
fact(5) = 120
fact(20) = 2432902008176640000
fact(21) = 51090942171709440000
fact(5) が 120。合っています。
fact(21) は、もう正しさが保証されない範囲に入っています。 Number がどの整数でも正確に表せるのは 9007199254740991 までで、fact(21) はそれを超えています(fact(21) と fact(22) はたまたま正確で、実際にずれ始めるのは fact(23) からです)。エラーは出ません。静かにずれます。 これは②でもう一度出てきます。
フォルダの容量を数える — 再帰が本当に効く形
階乗は正直、ループで書いたほうが簡単です。再帰が本当に効くのは、データそのものが入れ子になっているときです。フォルダはその代表です。
合計 = 11693 バイト
ここでのベースケースは if で書いていません。「中に何も無ければ for が1回も回らず、0 を返して終わる」が終わる条件です。再帰の終わりは、必ずしも if の形をしていません。
フォルダの中にフォルダがある構造を、ループで書こうとすると、自分でスタックを用意することになります。 入れ子の構造は、入れ子のまま書けるほうが読めます。 これが再帰を使う一番の理由です。
終わる条件を忘れると何が起きるか
わざと忘れます。
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 の正体)で見たものと同じです。
無限ループなら固まるだけですが、無限再帰は落ちます。 呼び出しごとに「戻り先」をスタックに積むので、メモリが先に尽きるからです。落ちてくれるのは、むしろ親切です。
どのくらい積めるのか数えます。
限界の深さ = 12529 / Maximum call stack size exceeded
約12,500段。 万単位の深さになる再帰は、それだけで危険だと分かります。③で戻ってきます。
📸 スクリーンショット①:
node nostop.mjsを打ってRangeError: Maximum call stack size exceededが出ている画面と、node depth.mjsの「限界の深さ」の行。エラーが「バグ」ではなく「積みすぎ」だと分かる並びにする。
② 同じ計算を何度もしている
ここがこの記事の中心です。
まず、遅さを測る
fib(30) = 832040 15.9 ms
fib(35) = 9227465 160.1 ms
fib(40) = 102334155 2133.4 ms
| n | 時間 | 前の行の何倍か |
|---|---|---|
| 30 | 15.9 ms | — |
| 35 | 160.1 ms | 10.1倍 |
| 40 | 2133.4 ms | 13.3倍 |
n を5足すたびに11倍前後。 n を1足すごとに約1.6倍です。これは O(2^n) に近い、指数的な伸び方です。
「データが10倍で100倍」だった O(n²) ですら、これに比べれば穏やかです(データが10倍で100倍遅くなる)。指数はグラフの形が違います。
何回呼ばれているのかを数える
推測ではなく、数えます。カウンタを1個足すだけです。
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) の呼び出しを、そのまま字下げで出してみます。
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行です。
fib(35) = 9227465 0.117 ms 呼び出し 69 回
fib(40) = 102334155 0.073 ms 呼び出し 79 回
fib(90) = 2880067194370816000 0.043 ms 呼び出し 179 回
並べます。
| n | 素朴な再帰 | メモ化 | 呼び出し回数(素朴 → メモ化) |
|---|---|---|---|
| 35 | 160.1 ms | 0.117 ms | 29,860,703 → 69 |
| 40 | 2133.4 ms | 0.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 の安全整数の上限を超えています。
Number.MAX_SAFE_INTEGER = 9007199254740991
BigInt fib(90) = 2880067194370816120
BigInt fib(200) = 280571172992510140037611932413038677189525
| 型 | fib(90) |
|---|---|
Number | 2880067194370816000 |
BigInt | 2880067194370816120 |
下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 の仕様には、これは入っています。 では効くのか、試します。
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 では成立しません。 私はここを「仕様にあるなら効くはず」と思い込んでいました。測るまで分かりませんでした。
ではどうするか — 自分でループにする
末尾再帰は、機械的にループへ書き換えられます。 引数が変数に、再帰呼び出しが代入になるだけです。
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種類の斜めだけです。斜めは 行 - 列 と 行 + 列 が一致するかで判定できます。
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 . . . .
枝刈りが全部だと、数で確かめる
「置けないと分かった時点で戻る」をやめて、全部置いてから最後に検査する版を書きます。
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 | 枝刈りあり | 枝刈りなし | 何倍 | 解の数 |
|---|---|---|---|---|
| 4 | 17 | 341 | 20倍 | 2 |
| 5 | 54 | 3,906 | 72倍 | 10 |
| 6 | 153 | 55,987 | 366倍 | 4 |
| 7 | 552 | 960,800 | 1,741倍 | 40 |
| 8 | 2,057 | 19,173,961 | 9,321倍 | 92 |
N=8 で 9,321倍。 そしてこの差は N が増えるほど開きます。
枝刈りなしは 8^8 = 1677万 通りの並べ方を全部作っています。枝刈りありは、「この列はもう埋まっている」と分かった瞬間に、その先の枝ごと捨てています。
バックトラックの速さは、探索の書き方ではなく「どれだけ早く諦めるか」で決まります。
N を伸ばすと、どこで壁に当たるか
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 | 解の数 | 調べた盤面 | 時間 | 前の行の何倍 |
|---|---|---|---|---|
| 8 | 92 | 2,057 | 1.7 ms | — |
| 9 | 352 | 8,394 | 10.5 ms | 6.2倍 |
| 10 | 724 | 35,539 | 27.0 ms | 2.6倍 |
| 11 | 2,680 | 166,926 | 127.8 ms | 4.7倍 |
| 12 | 14,200 | 856,189 | 687.9 ms | 5.4倍 |
| 13 | 73,712 | 4,674,890 | 4757.4 ms | 6.9倍 |
N を1増やすごとに、5〜7倍。これも指数です。
枝刈りをしても、指数は指数のままです。 定数倍が9000分の1になっただけで、伸び方の形は変わりません。N=20 は、この延長では終わりません。
これが「全部の組み合わせを調べる問題」の性格です。②のメモ化のように O(n) に落ちる魔法は、ここにはありません。
⑤ ナイトの巡回 — 順番を変えるだけで桁が変わる
同じバックトラックで、もう1つ。チェスのナイト(将棋の桂馬に似た動き)で、盤の全マスをちょうど1回ずつ通る経路を探します。
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.6ms | 25手 / 1.2ms |
| 7×7 | (0,0) | 7,151,179手 / 2.2s | 49手 / 0.9ms |
| 8×8 | (0,0) | 8,250,733手 / 1.7s | 64手 / 1.0ms |
| 8×8 | (3,3) | 5000万手で打ち切り / 12.2s | 64手 / 0.1ms |
| 10×10 | (0,0) | 5000万手で打ち切り / 10.3s | 100手 / 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通りで書く
重さの上限があるとき、価値の合計を最大にする選び方を求める問題です。旅行カバンに何を詰めるか、そのままです。
商品は毎回同じものにしたいので、擬似乱数を固定の種で作ります。
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 | 総当たり | メモ化再帰 | 動的計画法 |
|---|---|---|---|
| 10 | 0.6 ms | 0.50 ms | 0.38 ms |
| 15 | 2.9 ms | 0.51 ms | 0.25 ms |
| 20 | 12.2 ms | 1.41 ms | 0.23 ms |
| 25 | 27.8 ms | 1.44 ms | 0.26 ms |
| 30 | 204.1 ms | 1.29 ms | 9.2 ms |
総当たりの呼び出し回数を見ます。
| n | 呼び出し回数 |
|---|---|
| 10 | 1,826 |
| 20 | 332,790 |
| 25 | 1,963,966 |
| 30 | 9,336,151 |
5増えるごとにおよそ5〜6倍。 ②のフィボナッチと同じ形です。n = 60 は無理です。
メモ化の「表◯◯マス」に注目します。n = 30 で 4,190マス。930万回の呼び出しが、実は4,190通りしかない問いだったということです。
メモ化再帰と動的計画法は同じもの
2つを見比べます。
| メモ化再帰 | 動的計画法 | |
|---|---|---|
| 方向 | 大きいほうから始めて、必要になった小さい問いを解く | 小さいほうから順に全部埋める |
| 覚え場所 | Map(必要になったマスだけ) | 配列(全マス) |
| 呼ばれ方 | 再帰。スタックを使う | ループ。スタックを使わない |
| 無駄 | 無い(要るマスしか計算しない) | ある(使わないマスも埋める) |
やっている計算は同じです。順番と、覚える入れ物が違うだけです。
「動的計画法」という名前が難しそうなだけで、中身は「メモ化再帰を、下から順に書き直したもの」です。私はここが繋がるまで、別々の技だと思っていました。
n を伸ばして、差が出る場所を見る
--- 総当たりを外して 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 | メモ化再帰 | 動的計画法 | 差 |
|---|---|---|---|
| 50 | 2.7 ms | 0.07 ms | 39倍 |
| 200 | 25.2 ms | 0.15 ms | 168倍 |
| 1000 | 226.0 ms | 0.82 ms | 276倍 |
計算量は同じ O(n × 容量) なのに、実測で276倍開きました。差の中身は、
- 再帰の呼び出しそのもののコスト(引数を積んで、戻る)
Mapのハッシュ計算(10万件のincludesで止まる)- 動的計画法側は
Int32Arrayを連番で舐めるのでキャッシュに乗る(前の回で見たキャッシュの話)
計算量が同じでも、定数倍で276倍違います。 ただし、まず動くのはメモ化再帰のほうです。素朴な再帰にメモを足すだけなので、間違えにくい。 メモ化再帰で正しさを作ってから、必要なら動的計画法に書き直す。 この順番が現実的です。
⑦ 組み合わせと確率 — なぜハッシュはすぐ衝突するのか
再帰で「全部の並べ方」を作る話に戻ります。ここが実は、確率の入口です。
順列と組み合わせを、実際に列挙する
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万回シミュレーションします。
人数 | 実測(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%
| 人数 | 実測 | 理論 |
|---|---|---|
| 22 | 47.6% | 47.6% |
| 23 | 50.7% | 50.7% |
| 24 | 53.9% | 53.8% |
| 50 | 97.1% | 97.0% |
23人でちょうど50%を超えました。実測と理論が小数点1桁まで一致しています。
なぜ少ない人数で当たるのか。数えているのが「人数」ではなく「ペアの数」だからです。23人のペアは 23C2 = 253組。253回くじを引いているのと同じです。それなら 365 に対して半々になるのも分かります。
組み合わせの数え方(⑦の前半)が、そのまま確率の答えになっています。
これがハッシュの衝突が早い理由
前の回(10万件のincludesで止まる)で、ハッシュテーブルの衝突を見ました。「枠がたくさんあるのになぜ当たるのか」の答えが、これです。
枠 1,000 個 → 平均 41 個目で衝突(√枠数 = 32)
枠 1,000,000 個 → 平均 1,254 個目で衝突(√枠数 = 1,000)
枠 4,294,967,296 個 → 平均 79,907 個目で衝突(√枠数 = 65,536)
| 枠の数 | 平均で何個目に衝突するか | √枠数 |
|---|---|---|
| 1,000 | 41 | 32 |
| 1,000,000 | 1,254 | 1,000 |
| 約43億(32bit) | 79,907 | 65,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 の中です。そのまま消せます。
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
インストールしたものはありません(Node.js だけを使いました)。~/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万個で衝突。だから衝突処理は必須で、「めったに起きない」ではない
参考リンク
- roadmap.sh — Computer Science
- MDN — 関数(再帰)
- MDN — Map
- MDN — BigInt
- MDN — Number.MAX_SAFE_INTEGER
- MDN — RangeError
- ECMAScript 仕様 — Tail Position Calls
- Node.js — Performance measurement APIs
- MDN — Math.random
次に読む
この記事は 【深掘り】コンピュータ科学 の 15 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 最短経路アルゴリズム — ダイクストラは負の重みで壊れる |
| → 次の記事 | 文字列探索とKMP — grepは1文字ずつ見ていない |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- メモ化で指数が線形になる
- 枝刈りで探索量が桁で変わる
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント