では「再帰的にアルゴリズムを設計する思考法」を整理してみましょう。これまで具体例をたくさん見てきましたが、ここでは「どうやって再帰で考えるか」という“型”をまとめます。
再帰設計の基本ステップ
- 問題を小さく分ける
- 「大きな問題」を「同じ形の小さな問題」に分解できるかを考える。
- 例:
n! = n × (n-1)!、配列の合計 = 先頭 + 残りの合計。
- 終了条件（ベースケース）を決める
- 無限に潜らないように「ここで止まる」という条件を必ず設定する。
- 例:
factorial(0) = 1、空配列なら合計は0。
- 再帰ステップを定義する
- 「小さな問題を解いた結果」をどう組み合わせて答えを作るかを決める。
- 例:
sum(arr) = arr[0] + sum(arr.slice(1))。
- 戻りながら答えを組み立てるイメージを持つ
- 潜るときは「まだ未完成」、戻るときに「答えが積み上がる」。
思考法のフレームワーク
- ツリー構造を描いてみる
- 再帰呼び出しが「枝分かれ」するイメージを紙に書くと理解しやすい。
- 「もし小さいケースが解けるなら…」と考える
- 帰納法的な発想。「n-1が解けると仮定して、nをどう解くか？」
- ループに置き換えられるかを意識する
- 再帰で考えたあと「これはループの方が効率的かも」と判断できるようになる。
まとめ
- 再帰設計は 「分割 → 終了条件 → 再帰ステップ → 結合」 の流れで考える。
- 数学的な帰納法と同じ発想で「小さいケースが解けるなら大きいケースも解ける」と考える。
- 実務では「まず再帰でシンプルに考え、必要ならループに最適化」するのが王道。
👉 ここまでで「再帰の設計思考法」まで整理できました。
次は応用として「再帰を使ったパズル解法（ハノイの塔など）」を図解で追ってみると、再帰の美しさがさらに際立ちます。
