再帰とメモ化 — メモを1行足したら一瞬で終わった
フィボナッチを素直に書いたら fib(45) が返ってきませんでした。原因はアルゴリズムではなく、同じ引数を何千万回も計算し直していたことです。呼び出し回数を実際に数え、Map に覚えさせる1行を足して fib(90) が 0.04ms で返るところまでを実測します。あわせて末尾再帰が JavaScript では救いにならないことをスタックを溢れさせて確認し、N-Queen とナイトの巡回で「置く・進む・戻る」を書き、ナップサックを総当たり・メモ化再帰・動的計画法の3通りで測って並べます。最後に順列と組み合わせを列挙し、誕生日のパラドックスをシミュレーションしてハッシュの衝突に繋げます。