情報処理Ⅱ 第８回：２００３年１２月９日（火）

前回の講義の見直し 識別子の宣言（関数・変数の定義）に関する補足 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を呼び出している．

例題１のプロセス状態は？ 同一の変数名(x)に対して複数のオブジェクトが生成される点に注意． main countdown num = 3

例題１のバリエーション 出力の位置を変えると，countupになる． 再帰なしのプログラムのほうが，効率はよい． なぜ再帰なしのほうが効率がよいか？ …関数呼び出しのコストが大きいから． 「オーバーヘッド」という

再帰的な定義の例（１） 階乗 フィボナッチ数列（例題２） 再帰を用いれば，シンプルに書ける． 0! = 1, 1! = 1 n! = n×(n-1)!　(n≧2) フィボナッチ数列（例題２） a1 = 1, a2 = 1 an= an-1 + an-2 　(n≧3) 再帰を用いれば，シンプルに書ける． しかしこれらも，whileループのほうが効率がよい．

再帰的な定義の例（２） UNIXのファイル構造 「ディレクトリ」には「ファイル」を配置できる． ファイルには，「通常ファイル」と「ディレクトリ」がある（実際にはもっとさまざまな種類のファイルがある）． ディレクトリは「親ディレクトリ」をちょうど１つ持つ． etc X11 Sessions hosts XF86Config / home resolv.conf XF86Config-4 usr

そこで問題 あるディレクトリから下のすべてのファイル名を出力するには？ ディレクトリが持つファイルを（１個１個，順に）獲得すし，そのファイル名を出力する． それがディレクトリであれば，（再帰的に）そのディレクトリから下のすべてのファイル名を出力する． 本質的にこれは「木(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, }; …1 …2 …3 空白…0

再帰の使い方 関数プロトタイプは 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)) は式ではない．どうすれば判定（解析）できるか？ ⇒ 文字列（の先頭位置）を入力に取って，式，項，因数，定数をそれぞれ解析する関数を定義し，必要に応じて互いを呼び出し合えばよい．