アルゴリズムとデータ構造

アルゴリズムと
データ構造
第5回
再帰的アルゴリズム
再帰の基本

再帰（recursive）とは
 自分自身を含む、あるいは自分自身を用いて定
義される事象

再帰関数呼び出し
 関数が自分自身をさらに呼び出す

実際は自分自身と同じ関数を「別途」呼び出す
再帰の例：階乗値

階乗n!の定義
(a) 0! = 1
(b) n! = n × (n – 1)! (n > 0)
int factorial(int n) {
if (n > 0)
return (n * factorial(n – 1));
else
return (1);
}
/* 再帰的関数呼び出し */
再帰の例：階乗値

再帰関数呼び出しの流れ
int factorial(int n3210 ) {
if (n > 0)
2 1));
1
0
return ( 123n * factorial(n –
else
return (1);
}
factorial(3)
6
3 * factorial(2)
2
2 * factorial(1)
1
1 * factorial(0)
1
再帰の例：ユークリッドの互除法

2数の最大公約数
 2数を辺とする長方形を、あまりが出ない正方形
で埋め尽くす問題に置き換え

例：12と33
12
33
12
9
9
12
3
3 3 3
再帰の例：ユークリッドの互除法

最大公約数を求める手順
(a) 大きい方の数を小さい方の数で割ったあまりを
求める
(b) あまりが0になるまで、小さい方の数を大きい方
の数、あまりを小さい方の数として繰り返す

数学的手順
 最大公約数gcd(x,
ればgcd(y, x % y）
y)は、yが0ならx、そうでなけ
再帰の例：ユークリッドの互除法

関数実装例
int gcd(int x, int y) {
if (y == 0)
return (x);
else
return (gcd(y, x % y));
}
/* 再帰的関数呼び出し */
再帰アルゴリズムの解析

解析用関数
int recur(int n) {
if (n > 0) {
recur(n – 1);
printf(“%d\n”, n);
recur(n – 2);
}
・関数内で2度再帰呼び出し：真に再帰的な関数
再帰アルゴリズムの解析

トップダウン解析（n=4の場合）
recur(3)
recur(2)
recur(1)
recur(0)
1
2
recur(-1)
recur(0)
3
4
recur(2)
recur(1)
recur(1)
recur(0)
1
recur(-1)
recur(0)
1
2
recur(0)
recur(-1)
再帰アルゴリズムの解析

ボトムアップ解析（n=4の場合）
recur(-1) : （何もしない）
recur(0) : （何もしない）
recur(1) : recur(0) 1 recur(-1) →
1
recur(2) : recur(1) 2 recur(0)
→
1
2
recur(3) : recur(2) 3 recur(1)
→
1
2
3
1
recur(4) : recur(3) 4 recur(2)
→
1
2
3
1
4
1
2
再帰を使うべきか

再帰の問題点
 関数呼び出しの状態を保存しておくため、膨大な
メモリが必要
 関数呼び出しのオーバーヘッドなどで、計算時間
が増大する可能性大

再帰にすべきかどうか
 非再帰で実現できるなら非再帰を用いるべき
 非再帰では複雑になりすぎるなら再帰を用いる
ハノイの塔

ハノイの塔とは
 固定された3本の柱のうちの１本に、下へ行くほ
ど半径の大きい円盤
 以下のルールで別の1本に円盤をすべて移動
1回に動かせる円盤は1枚
 半径の小さい円盤の上に半径の大きい円盤は重ねら
れない
 棒以外の部分には円盤は置けない

ハノイの塔

移動例（3枚の場合）
1
1
2
1
2
3
1
2
3
1
ハノイの塔

一般的な解法の考え方
1
1
2
1
2
3
2
3
開始軸
中間軸
目的軸
ハノイの塔

ハノイの塔の解法
底の円盤を除いた円盤グループを開始軸から
中間軸に移動
2. 底の円盤を開始軸から目的軸に移動
3. 円盤グループを中間軸から目的軸に移動
 1.と3.で再帰呼び出し
1.
ハノイの塔

ハノイの塔の解法
1
2
1
3
2
開始軸
中間軸
目的軸
目的軸
中間軸
ハノイの塔

関数実装例
void move(int no, int x, int y) {
if (no > 1)
move(no - 1, ｘ, 6 - x - y);
printf(“[%d]を軸%dから軸%dへ移動\n”, no, x, y);
if (no > 1)
move(no - 1, 6 - x - y, y);
}
・1 : 開始軸、2 : 中間軸、3 : 目的軸
8王妃問題

8王妃問題とは
 8x8のチェス盤に、8個の王妃を互いに取られな
いように配置
王妃は縦横斜めいずれのライン上のコマも取ることが
できる
 縦横斜めいずれのラインにも別の王妃がないように配
置しなければならない

8王妃問題

王妃の配置
 何も考えないと、64x63x62x61x60x59x58x57
=
178,462,987,637,760通り
 各列に王妃を1個のみ配置と限定すると、
8x8x8x8x8x8x8x8 = 16,777,216通り
 各行にも王妃を1個のみ配置と限定すると・・・簡
単には計算できない
8王妃問題

王妃の配置
 まず各列1個のみの方針で組み合わせを列挙
8王妃問題

王妃の配置
 各行にも王妃を1個ずつ配置するよう限定する操
作を導入
 flagを導入し、すでに配置されている行のflagを
立てておく
 flagの立っている行には配置作業を行わない
 必要のない枝分かれを抑制して、不要な組み合
わせの列挙を省略：分枝限定法
8王妃問題

王妃の配置
 各行にも1個のみの方針で組み合わせを列挙
8王妃問題

王妃の配置
 斜めのラインにも1個ずつ配置されるよう限定す
る操作を導入
 右上がり、右下がり両方向に別々のflagを導入し、
すでに配置されているラインのflagを立てておく
 flagの立っているラインには配置作業を行わない

Download Report