分割統治法

分割統治法（ぶんかつとうちほう、）は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。
擬似コード.
分割統治法を擬似コードによって表現すると、以下のような再帰呼出しを使ったものとなる。また、分割統治法になっている何らかのアルゴリズムを実装すると、その基本的な骨組みがこのようになる。
 function conquer(x) is
 if xは簡単にconquerできる then
 return conquerの結果
 else
 (x1, x2, ...) := divide(x) // 複数の小さな副問題に分割
 (y1, y2, ...) := (conquer(x1), conquer(x2), ...) // 再帰
 return synthesize(y1, y2, ...) // 各副問題の解を合成（最大値を選ぶ、等）
具体的なアルゴリズムのサンプルとしては、マージソートの記事などを参照。
その他.
分割統治法は、再帰の際に同じ副問題を複数回解いてしまう場合があり、そうした場合にはそれが原因で計算コストが、計算を終えるのが非現実的になるほどに増加（例えば指数的に発散して）しまう事がある。この問題はメモ化で解決できることがある。最初からメモ化を組込んだ手法の例に、動的計画法がある。
（以下はこの手法に限らず一般的な話であるが）再帰呼出しを使ったプログラムでは、再帰が深くなるとスタックが大きく成長し、メモリが足りなくなったり最悪の場合はスラッシングを起こす。再帰をループに書換える手法もあるが、直接の末尾再帰からの書換えでなければ、結局自分で管理するスタックにデータを積むため、労が多いわりに益が少ないこともある。キューを実装に使うこともあるが、それは速度の問題などよりは、縦ではなく横に探索したい（幅優先探索をしたい）といった理由による。