パズル問題解法のアルゴリズム講座
入門編
新たなる魔物「再帰」
１．奇妙な「国語辞典」
あなたがもし「折半」という言葉の意味を知りたくて国語辞典を調べたとします。すると、こう書いてありました。「折半」とは、金銭等を二人で折半すること。
こんな国語辞典はありません。「折半」を説明するのに「折半」という言葉を使うのはおかしい。
あなたは、そう思うかも知れません。でも、プログラムの世界では人工知能の研究の過程で、このような
記述を可能にしているのです。そしてあなたも「数学的帰納法」という名称で学校の数学の時間に学んで
いるかも知れません。
２．「再帰」とは
再帰を説明するのに、よく利用されるのが「階乗」の計算方法です。階乗とは、例えば５の階乗は、５×４×３×２×１＝１２０
という計算ですね。通常、この階乗計算のプログラムは次のようなものです。
int kaijyo(int n) {
int i, ans=1;
for (i=n; i > 1; i--)
ans = ans * i;
return ans;
}
しかし、「再帰」を用いるとこんなプログラムになります。
int kaijyo(int n) {
int ans;
if (n < 2) ans = 1;
else ans = n * kaijyo(n-1);
return ans;
}
kaijyo(n)の関数を定義するのに、kaijyo(n-1)を使用しています。５の階乗計算はこうなります。
kaikyo(5) = 5 * kaijyo(4)
= 5 * (4 * kaijyo(3))
= 5 * (4 * (3 * kaijyo(2)))
= 5 * (4 * (3 * (2 * kaijyo(1))))
= 5 * (4 * (3 * (2 * 1 ))) (kaijyo(1)は1である)
= 120
このようにして、確かに答えが出ます。「再帰」を使用する上で大切なことは、「終着点」を設けて、必ずこの終着点に到達するようにしておくことです。
パズル問題をプログラムで解く場合、この「再帰」が大活躍します。