情報処理Ⅱ 第８回：２００３年１２月９日（火）前回の講義の見直し   識別子の宣言（関数・変数の定義）に関する補足 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)) は式ではない．どうすれば判定（解析）できるか？ ⇒ 文字列（の先頭位置）を入力に取って，式，項，因数，定数をそれぞれ解析する関数を定義し，必要に応じて互いを呼び出し合えばよい．