情報処理Ⅱ

情報処理Ⅱ
第８回：２００３年１２月９日（火）
前回の講義の見直し


識別子の宣言（関数・変数の定義）に関する補足
constを含む変数と代入
識別子の宣言に関する補足

グローバル区間に同一の識別子を複数宣言できない．


ブロック内（ローカル）に変数を定義するときは，それ
より外の識別子と重複してもよい．




ブロック内では，重複する外の識別子は使用できない．
モジュール化に関して有用なルール．
関数はブロック内で定義できない．


関数と同じ名前の変数もNG．
必ずグローバル区間での定義となる．
グローバル - global - 大域的 - あらゆるブロックの外
ローカル - local - 局所的 - あるブロックの中
constを含む変数と代入


constを含む型について，オブジェクトの参照はOK．
代入など，左辺値としての使用はよくない（警告）．
ポインタの代入について
const char *p; char *q;としたとき，
 constなしからconstあり(p = q;)はOK．
 constありからconstなし(q = p;)はよくない（警告）．
 キャスト演算子による変換(q = (char *)p;)はOK．

記憶域クラスには適用できない（型の一部ではない）．

x = (static int)y; はNG（コンパイルエラー）．
本日のテーマ：再帰(recursion)



Cでは，関数の内部で自分自身を呼び出す（再帰呼び出
し，recursive call）ような記述ができる．
再帰的（帰納的，循環的）な定義の実装や，バックト
ラック(backtrack)，分割統治法(divide-and-conquer)と
いった手法に対してよく用いられる．
注意点


無限ループにならないようにする．
再帰を使わないほうがよいこともある．
例題１


カウントダウンするプログラム
自作関数countdownの定義の中で，countdownを呼び出
している．
例題１のプロセス状態は？
main
num = 3
countdown
x=3
countdown
x=2
countdown
x=1

同一の変数名(x)に対して
複数のオブジェクトが生
成される点に注意．
countdown
x=0
例題１のバリエーション


出力の位置を変えると，countupになる．
再帰なしのプログラムのほうが，効率はよい．

なぜ再帰なしのほうが効率がよいか？ …関数呼び出しのコ
ストが大きいから．
「オーバーヘッド」という
再帰的な定義の例（１）

階乗





(n≧2)
フィボナッチ数列（例題２）


0! = 1, 1! = 1
n! = n×(n-1)!
a1 = 1, a2 = 1
an= an-1 + an-2
(n≧3)
再帰を用いれば，シンプルに書ける．
しかしこれらも，whileループのほうが効率がよい．
再帰的な定義の例（２）

UNIXのファイル構造



「ディレクトリ」には「ファイル」を配置できる．
ファイルには，「通常ファイル」と「ディレクトリ」があ
る（実際にはもっとさまざまな種類のファイルがある）．
ディレクトリは「親ディレクトリ」をちょうど１つ持つ．
etc
/
home
usr
X11
Sessions
hosts
XF86Config
resolv.conf
XF86Config-4
そこで問題

あるディレクトリから下のすべてのファイル名を出力す
るには？



ディレクトリが持つファイルを（１個１個，順に）獲得す
し，そのファイル名を出力する．
それがディレクトリであれば，（再帰的に）そのディレク
トリから下のすべてのファイル名を出力する．
本質的にこれは「木(tree)の探索問題」であり，さまざ
まなアルゴリズムが知られている．
例題３：ぷよ連結問題

右図のような（２次元）
フィールドと，その中の
座標を入力に取り，そこ
と連結する「ぷよ」の個
数を求めよ．
フィールドの表現


フィールドは２次元 ⇒２次元配列を使用
色は赤・青・黄と空白 ⇒int型で表現
int field[高さ][幅] = {
0, 0, 3, 0, 0, 0,
1, 3, 2, 0, 0, 1,
3, 2, 3, 2, 2, 2,
3, 2, 2, 3, 3, 3,
1, 1, 2, 3, 1, 3,
1, 1, 2, 2, 3, 3,
};
空白…0
…1
…2
…3
再帰の使い方

関数プロトタイプは int consize(int x, int y, int color);



(x, y)と連結していて色がcolorである「ぷよ」の数を返す．
フィールド情報は，関数の「外」から与える．
戻り値は，


（探索打ち切りの）条件を満たすときは，0
そうでなければ，
1
+ consize(x + 1, y, color)
+ consize(x - 1, y, color)
+ consize(x, y + 1, color)
+ consize(x, y - 1, color)
: 探索の方向
探索打ち切りの条件

以下のいずれか





(x, y)が範囲外
color == 0
field[y][x] != color
(x, y)の地点は探索済み
探索済みかどうかを記憶するための領域も必要．

int field_checked[高さ][幅]; で確保する．
分割統治法


対象領域を細分化して求め（分割），全体として正しい
解になる（統治）ようにする．
例: クイックソート
「４より小」，
「４と等しい」，
「４より大」に
分ける．
４７２６１８３５
２１３４７６８５
１２３４６５７８
１２３４５６７８
まとめ


再帰的に定義された問題は，再帰呼び出しを用いてプロ
グラムを記述するとうまくいきやすい．
一般に，再帰を用いないほうが効率的である．

関数内のauto変数は，関数呼び出しごとに生成される点に
注意．
レポートの補足

「レポートの書き方」を作成したので参考にしてほしい．


http://www.wakayama-u.ac.jp/~takehiko/ipii2003/report.pdf
講義のページからリンクしている．
発展的な話題：
再帰は常に解消できるか？


結論から言うと，可能．
方法は…

反復に置き換える．


「スタック」や「リスト」と呼ばれるデータ構造を用いる．


簡単な数列の問題は，これで可能．
木の探索，ぷよ連結問題，クイックソートともこれで可能．
注意点


自然でない記述になるため，バグが入りやすい．
かける手間に対して効率がよくなるかの検討が必要．
発展的な話題：
自分自身を呼び出さない再帰


関数 x が関数 y を呼び出し，関数 y が関数 x を呼び出す場合も再帰
という．
例: 再帰下降構文解析
 「式」は，「項」,「項+項」,「項+項+項」… のいずれかにより
構成される．
 「項」は，「因数」,「因数*因数」,「因数*因数」,「因数*因数*
因数」…のいずれかにより構成される．
 「因数」は，「(式)」もしくは「定数」により構成される．
 5 や 1+2*3 はこの意味で式であるが，2++ や (4)) は式ではない．
どうすれば判定（解析）できるか？
⇒ 文字列（の先頭位置）を入力に取って，式，項，因数，定数
をそれぞれ解析する関数を定義し，必要に応じて互いを呼び出
し合えばよい．

Download Report