情報処理Ⅱ ２００７年１２月３日（月） その２

本日学ぶこと 再帰(recursion) ⇒自己言及なくして情報技術を語るなかれ ライブラリ関数 ⇒先人の知恵を拝借 ライブラリ関数 ⇒先人の知恵を拝借 共通するキーワード：関数の活用

前回の補足：関数の抽出 関数を抽出することで一般に 関数抽出の要点 コード量（プログラムのサイズ，ステップ数）は増える． しかし，それぞれの関数のコード量は減り，関数ごとに役割が明確になるため，読みやすい． 関数抽出の要点 ①関数名，②戻り値の型，③仮引数 の順に決める． 変数の有効範囲に注意する． 仮引数と実引数が同じ名前でも，別オブジェクト． 変数の除去や複製が必要なこともある． 保守性向上

再帰呼び出しとは 関数の内部で自分自身を呼び出すことを，再帰呼び出し(リカーシブコール，recursive call)という． 用途 注意点 再帰的（帰納的，循環的）な定義 バックトラック(backtrack) 分割統治法(divide-and-conquer) 注意点 無限ループにならないようにする． 再帰を使わないほうがよいこともある． 「データ構造とプログラ ミング技法」他で リp.121, pp.363-364

階乗を求める関数 階乗 プログラムコード 0! = 1, 1! = 1 n! = n×(n-1)! (n≧2) int factorial(int x) { if (x <= 1) return 1; else return x * factorial(x - 1); } 関数factorialの中で 関数factorialを 呼び出している…再帰！ factorial.c

なぜ再帰呼び出しが可能なのか？ 同一の変数名x に対して複数の このようなデータ 構造を，「スタック」 オブジェクトが という． 生成される． このようなデータ 構造を，「スタック」 という． factorial x = 1 factorial x = 2 factorialの再帰呼び出しを終えたときの戻り先 factorialの呼び出し（関数処理）を終えたときの戻り先 factorial関数処理時に 生成されるオブジェクト main x = 3 Cの規格として「スタック」が必須ということではない． しかし，関数呼び出しの構造(mainから関数Aを呼び出し，関数Aの中で関数Bを呼び出し，関数Bの処理を終えたら， 制御は，mainではなく，「関数Aの中で関数Bを呼び出したところ」に戻らなければならない(そして，関数Aの処理を 終えたら，制御は，mainの中で関数Aを呼び出したところに戻る))を実行時に保持するには，スタックが最も合理的 ということである． main関数処理時に 生成されるオブジェクト num = 3 入p.285

カウントダウン，カウントアップ countdown(5); ⇒ 5 4 3 2 1 0 countup(5); ⇒ 0 1 2 3 4 5 カウントアップ，カウントダウンともに，再帰呼び出しなしの プログラムのほうが，効率はよい． なぜ再帰呼び出しは効率が悪いか？ …関数呼び出しのコスト（オーバーヘッド）があるから． 業務としてのプログラミングで，再帰呼び出しを使用してはならないと（コーディング規約で）定めていることも 再帰呼び出しはしてはいけないと書いている例: 『組み込みソフトウェア開発向けコーディング作法ガイド』p.49 『ずっと受けたかったソフトウェアエンジニアリングの授業2』pp.121-122 countdown.c, countup.c

再帰的な定義の例（１） 階乗 フィボナッチ数列 最大公約数 再帰呼び出しを用いれば，シンプルに書ける． 0! = 1, 1! = 1 n! = n×(n-1)!　(n≧2) フィボナッチ数列 a1 = 1, a2 = 1 an = an-1 + an-2 　(n≧3) 最大公約数 gcd(n,0) = 0 gcd(n,m) = gcd(m,n%m) (m>0) 再帰呼び出しを用いれば，シンプルに書ける． しかしこれらも，whileループのほうが効率がよい． 最大公約数の式について，n=0や，n<mのときにも成り立つ． （例：gcd(0, 5) = gcd(5, 0) = 0; gcd(9,12) = gcd(12,9) = gcd(9,3) = gcd(3,0) = 3）

再帰的な定義の例（２） 木構造 再帰呼び出しは必要？ トーナメント表の決勝戦から順に見て， 優勝チームの戦績を知る 100万個の記録から，欲しいものを 瞬時に獲得する ホームディレクトリ以下のすべての ファイル名を出力する 再帰呼び出しは必要？ するのが自然な場合と，してはいけない 場合がある 呼び出し方よりもデータ構造のほうが重要 「100万個～瞬時に獲得する」と木構造の結びつきは自明でないが，2年後期の「データベース」で学んでほしい． 「ホームディレクトリ以下のすべてのファイル名を出力する」には，いちいちプログラムを作らなくても， 「find ~」を実行するだけでいい．

再帰的な定義の例（３） 文法 計算機でどう処理する？ BNF記法 <識別子> ::= <識別子> <英字> | <識別子> <数字> | <識別子> '_' | <英字> | '_' 句構造文法による式の定義 計算機でどう処理する？ 字句解析・構文解析を行う． 再帰下降構文解析は，文法と対応した 解析器（パーサ）を生成するが，効率は 必ずしも良くない． a=b++-+c; ↓ 字句解析 構文解析 OK a=b++++c; NG 再帰下降構文解析 http://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0%E4%B8%8B%E9%99%8D%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90 構文解析などに関する基本書籍：中田育男: コンパイラ, 産業図書, 1981. 「b(符号) (符号) (符号) (符号)c」の式で文法的に正しいものはどれか検証している文献：Lepton: Lepton先生のCの強化書, 翔泳社, pp.217-225, 2007. リpp.170-172

次に学ぶこと ライブラリ関数の活用 （参考）関数の分類 先人の知恵を活用する． 勉強・授業のためでなければ， ライブラリ関数と同じ名前や機能の関数は自作しない． （参考）関数の分類 自作関数: 自分で定義する．⇒ １１月２６日のテーマ ライブラリ関数: 出来合いのもの．printfなど．⇒ ここでのテーマ 入p.111

ライブラリ 関数・定数・独自型などをまとめて，他のプログラムから利用できるよう部品化したものを「ライブラリ」という． ライブラリ関数の分類 標準ライブラリ関数（標準関数，ANSI準拠の関数） 情報処理Ⅱで使用するのは，この範囲だけ POSIX準拠の関数 情報ネットワーク演習で使用する その他（サードパーティライブラリ） OpenGL（ビジュアル情報演習で使用する） など http://ja.wikipedia.org/wiki/POSIX ANSI: American National Standard Institute POSIX: Portable Operating System Interface for UNIX リp.346

ライブラリ関数とヘッダファイル 既に定義されている関数や定数を利用するには，あらかじめ，適切なファイル名（ヘッダファイル）を記載しておく． printf なら #include <stdio.h> CHAR_BIT なら #include <limits.h> ライブラリ関数と，記載すべきヘッダファイル名は，オンラインマニュアルで知ることができる． man 3 printf jman 3 printf JM Project (http://www.linux.or.jp/JM/) ヘッダファイルはコンパイル環境が保有しているが，その所在は，環境による． Vine Linuxでおすすめ リp.369の最後に「詳細は，27.10節を参照して下さい．」とあるが，27.10節は存在しない． 入p.114 リp.369, pp.395-396, p.473, p.421

ヘッダファイルとインクルード ヘッダファイルには，定数，構造体や特殊な型，関数プロトタイプなどが宣言されている． #include <stdlib.h> とすると，/usr/include/stdlib.h を取り込む（インクルードする）． 慣例として，ファイル名は「.h」で終わらせる． ヘッダファイルの中で，他のヘッダファイルをインクルードすることもよく行われる． ヘッダファイルを自作することもある．そのファイルをインクルードするときは，#include "headerfile.h" のように書く． 「.c」や「.h」などを，Windowsユーザは「拡張子」と呼んでいるが， Unix文化では「サフィックス(suffix)」と呼ばれている． リp.395-396

有用なライブラリ関数（１） #include <stdio.h> を必要とするもの int printf(const char *format, ...); int scanf(const char *format, ...); int putchar(int c); … 1文字出力 int getchar(void); …　1文字入力 int sprintf(char *str, const char *format, ...); … printfと同様に文字列を構成し，結果をstr（の指し示す配列領域）に格納する 可変引数 と呼ばれる 可変引数 と呼ばれる リp.455, p.139

有用なライブラリ関数（２） #include <stdlib.h> を必要とするもの int atoi(char *s); … 文字列から整数値への変換 void exit(int status); … プログラムの終了 int rand(void); … 乱数生成 #include <string.h> を必要とするもの size_t strlen(char *s); … 文字列の長さ int strcmp(char *s1, char *s2); … 文字列比較 char *strstr(char *s1, char *s2); … 文字列検索 char *strcat(char *dest, char *src); … 文字列連結 #include <string.h>を必要とするものについて， strcatのdestを除き，char *型の仮引数には，constがつく． リp.493, p.511

有用なライブラリ関数（３） #include <ctype.h> を必要とするもの int isdigit(int c); … 文字が数字であるか判定 isalphaは英字判定，isalnumは英数字判定 int tolower(int c); … 大文字を小文字に変換 大文字以外の文字はそのまま 逆はtoupper #include <math.h> を必要とするもの double exp(double x); … eのx乗 double floor(double x); … x以下で最小の整数 最大はceil，四捨五入（丸め）はround コンパイル時，「cc -lm program.c」のようにリンカオプション(linker option)が必要 リp.411, p.432

関数名の表記 printf関数，関数printf printf()関数，関数printf() printf(3) この授業で採用している． 関数名であることを明確にする表記法．よく見かける． printf(3) 「printfというライブラリ関数があって，詳細は， man 3 printfを実行すれば得られる」の意味． 「(1)」ならコマンド，「(2)」はシステムコール man printfを実行すると，ライブラリ関数ではなく，コマンドとしてのprintfの使い方が出てくる． 「printfの実引数に3と書く」ではない．

まとめ 再帰呼び出しを用いて関数を定義すると，プログラムがすっきり書けることがある． 一般に，再帰を用いないほうが効率的である． 再帰的に定義された問題に適用すると，効果的． 一般に，再帰を用いないほうが効率的である． 関数内のauto変数は，関数呼び出しごとに生成される． ライブラリ関数の活用により，先人の知恵を活用しながら，信頼性の高いソフトウェアが作れる． 関数名，処理内容，ヘッダファイル，引数，戻り値を把握する． 教科書だけでなく，オンラインマニュアルやインターネットの情報も参考に．