再帰と分割統治

再帰関数

再帰関数とは、関数の中で自分自身を呼び出すような関数で、アルゴリズムを実装するためのプログラミングテクニックの1つである。例えば、整数nの階乗を計算する関数は再帰関数として定義することができる。

factional(n)
  if n == 1
    return 1
  return n * factional(n - 1)

nの階乗は、n! = n x (n -1) x (n - 2)... x 1 = n x (n - 1)!であり、nが1より大きい場合は、より小さい部分問題である「(n - 1)の階乗」を含んでいる。そのため、パラメタnを減らして同じ機能を持つ関数、つまり自分自身を適用し、元の問題の計算に利用することができる。nが1のときは、1を返すというように、再帰関数はそれが必ずどこかで終了するように実装する必要がある。

分割統治

分割統治法は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。

再帰のテクニックを用いると、ある問題を2つ以上の小さい問題に分割して、再帰関数によりそれぞれの部分問題の解を求め、それらの結果を統合することにより、元の問題の解を求めることができる場合がある。このようなプログラミングの手法を分割統治法と呼び、以下の手順に基づきアルゴリズムが実装される。

1.与えられた問題を部分問題に分割する。
2.部分問題を再帰的に解く。
3.得られた部分問題の解を「統合」して、元の問題を解く。