はじめに

先日行われた AtCoder Beginner Contest 427 の B 問題で、思いのほか苦戦してしまいました。
これは「メモ化再帰」を使うときれいに解けるタイプの問題だったのですが、いい機会なので整理しておこうと思い、いくつかのメモ化再帰の練習問題を解いてみました。

参考にしたのは Zenn のこちらの記事👇
👉 AtCoder典型問題分類 6 再帰関数・メモ化再帰

🧠 再帰と計算量の爆発

Haskell では for ループのような命令的な構文ではなく、ふつうは再帰を使って処理を繰り返します。
たとえば 1 から n までの和は次のように書けます。

f 1 = 1
f n = n + f (n - 1)

このような「直線的な」再帰なら計算量は O(n) で問題ありません。

しかし、f n を求めるために f (n-1) と f (n-2) のように複数の再帰呼び出しをする場合、
同じ計算を何度も行ってしまい計算量が爆発します。

こういうときに有効なのが「メモ化（一度計算した結果を覚える）」です。

🪜 1. 次々に項を求めるタイプ（ボトムアップ）

ABC273 A 問題

factorial を計算するシンプルな例です。

f 0 = 1
f k = k * f (k - 1)

これは n から順に計算していくため爆発しません。
ただし、複数の値を map f [1..n] のように一気に計算しようとすると同じ計算が重複します。

unfoldr で下から順に構築

Haskell では unfoldr を使い、小さい項から順に factorialを構築することで、
自然にメモ化と同等の効果を得られます。

import Data.List (unfoldr)

fs :: [Integer]
fs = unfoldr (\(b, k) -> Just (b, (b * succ k, succ k))) (1, 0)
-- 1, 1, 2, 6, 24, ...

(b, k) は「現在の factorial 値」と「現在のステップ」を保持
b を出力し、次の状態 (b*(k+1), k+1) へ進めている

👉 こうして fs を使えば f 0, f 1, f 2… が O(n) で計算できます。

🪄 2. 前の項を2回使うタイプ（再帰の爆発）

ABC247 C 問題

この問題では次のような再帰が定義されています：

s 1 = [1]
s n = s (n - 1) ++ [n] ++ s (n - 1)

このままでも n ≤ 16 なら間に合いますが、s (n-1) を 2 回呼び出すため
n が大きくなると計算量が指数的に膨れ上がります。

unfoldr でボトムアップ構築

これも unfoldr を使えば一度計算した s (n-1) を再利用できます。

import Data.List (unfoldr)

ss :: [[Int]]
ss = unfoldr (\(b, k) -> Just (b, (b ++ [succ k] ++ b, succ k))) ([1], 1)

ss の要素は

s(1) = [1]
s(2) = [1,2,1]
s(3) = [1,2,1,3,1,2,1]
...

のように順に構築されます。

📎 提出例（AtCoder）

🪄 3. 飛び飛びの値を計算するタイプ（トップダウン）

ABC275 D 問題

f(0) = 1
f(n) = f(n `div` 2) + f(n `div` 3)

このような場合、f 0 → f 1 → f 2 と順に作ることができません。
値が n div 2 や n div 3 など 飛び飛び で呼ばれるからです。

👉 このような場合は Map などを使って トップダウンでメモ化 します。

import qualified Data.Map.Strict as M

main :: IO ()
main = do
  n <- readLn :: IO Int
  print $ f n

f :: Int -> Integer
f n = snd (go M.empty n)
  where
    go memo 0 = (M.insert 0 1 memo, 1)
    go memo x =
      case M.lookup x memo of
        Just v  -> (memo, v)
        Nothing ->
          let (memo1, a) = go memo (x `div` 2)
              (memo2, b) = go memo1 (x `div` 3)
              v = a + b
          in (M.insert x v memo2, v)

計算済みの値は Map に記録
未計算のときのみ再帰して値を登録
計算量を大幅に削減できます

📊 まとめ：ボトムアップとトップダウンの使い分け

パターン	特徴	対応策	例
直線的な再帰	`f n` → `f (n-1)`	そのままで OK	階乗など
下から順に計算できる	`f n` を作るのに `f (n-1)` が必要	`unfoldr` などでボトムアップ	ABC273A, ABC247C
飛び飛びの値を使う	`f n` → `f (n div 2)` など	`Map` でトップダウンメモ化	ABC275D

🏁 おわりに

再帰関数は素直に書いても動きますが、
計算量が爆発しないか を意識してパターンに応じた最適化を行うことで
より幅広い問題に対応できるようになります。

📈 unfoldr で下から順に作る → ボトムアップ型
🧭 Map で結果を覚える → トップダウン型

AtCoder のメモ化再帰系の問題も、この2パターンを押さえるとかなり解けるようになります。
Haskell でも実戦的に戦えると実感しました💪

📚 参考

追記(unfoldrの代わりにiterateを使用する)

今回の記事ではunfoldrを使用しましたが処理の途中で止める必要がない場合はiterateが最適です。

Haskellで「現在から未来を作る」処理と `iterate` の相性が抜群な理由

iterate は、まさに「現在から未来を作る」処理と相性が抜群です。
iterate f x は、x から始めて f を何度も適用し続ける無限リストを生成する関数です。

`iterate` を使って未来を作る

iterate の型は次のようになっています：

iterate :: (a -> a) -> a -> [a]

つまり、「次の状態を作る関数」と「初期状態」を与えれば、
それを無限に適用してリストにしてくれます。

`go` 関数を `iterate` で書き換える

以前、自分で再帰を書いて未来を作る処理をしていたもの（例：go 関数）は
iterate を使うと非常にシンプルに置き換えられます👇

factorials :: [(Integer, Integer)]
factorials = iterate g1 (1, 0)
  where
    g1 (b, k) = ((k + 1) * b, k + 1)

ここでは

(b, k) が現在の状態（b は階乗値、k はインデックス）
g1 が「次の状態を作る関数」
(1, 0) が初期状態（0! = 1）

実行例

take 10 $ map fst factorials
-- => [1,1,2,6,24,120,720,5040,40320,362880]

iterate は

初期値 → 関数適用 → 次の値 → ...

という流れを内部で勝手にやってくれるので、自分で再帰を書く必要がなくなります。
✅ 無限列を作るときにまず iterate を思い出すと、
再帰をゴリゴリ書かずに、すっきりと書けるようになります ✨