情報処理II

情報処理Ⅱ
2007年12月3日(月)
その2
本日学ぶこと



再帰(recursion)
⇒自己言及なくして情報技術を語るなかれ
ライブラリ関数
⇒先人の知恵を拝借
共通するキーワード:関数の活用
2
前回の補足:関数の抽出

関数を抽出することで一般に



コード量(プログラムのサイズ,ステップ数)は増える.
しかし,それぞれの関数のコード量は減り,関数ごとに役割が
明確になるため,読みやすい.
関数抽出の要点



保守性向上
①関数名,②戻り値の型,③仮引数 の順に決める.
変数の有効範囲に注意する.
• 仮引数と実引数が同じ名前でも,別オブジェクト.
変数の除去や複製が必要なこともある.
3
再帰呼び出しとは


関数の内部で自分自身を呼び出すことを,再帰呼び出し(リ
カーシブコール,recursive call)という.
用途




再帰的(帰納的,循環的)な定義
バックトラック(backtrack)
分割統治法(divide-and-conquer)
「データ構造とプログラ
ミング技法」他で
注意点


無限ループにならないようにする.
再帰を使わないほうがよいこともある.
リp.121, pp.363-364
4
階乗を求める関数

階乗



0! = 1, 1! = 1
n! = n×(n-1)! (n≧2)
プログラムコード

int factorial(int x)
関数factorialの中で
{
関数factorialを
if (x <= 1)
呼び出している…再帰!
return 1;
else
return x * factorial(x - 1);
}
factorial.c
5
なぜ再帰呼び出しが可能なのか?
このようなデータ
構造を,「スタック」
という.
x=1
同一の変数名x
に対して複数の
オブジェクトが
生成される.
factorial
x=2
factorial
factorial関数処理時に
生成されるオブジェクト
x=3
main
main関数処理時に
生成されるオブジェクト
入p.285
factorialの再帰呼び出しを
終えたときの戻り先
num = 3
factorialの呼び出し(関数
処理)を終えたときの戻り
先
6
カウントダウン,カウントアップ




countdown(5);
⇒ 5 4 3 2 1 0
countup(5);
⇒ 0 1 2 3 4 5
countdownとcountupの違いは,「出力」と「再帰呼び出
し」の前後関係だけ
カウントアップ,カウントダウンともに,再帰呼び出しなしの
プログラムのほうが,効率はよい.


なぜ再帰呼び出しは効率が悪いか?
…関数呼び出しのコスト(オーバーヘッド)があるから.
業務としてのプログラミングで,再帰呼び出しを使用してはなら
ないと(コーディング規約で)定めていることも
countdown.c, countup.c
7
再帰的な定義の例(1)

階乗



フィボナッチ数列





a1 = 1, a2 = 1
an = an-1 + an-2
(n≧3)
最大公約数


0! = 1, 1! = 1
n! = n×(n-1)! (n≧2)
gcd(n,0) = 0
gcd(n,m) = gcd(m,n%m)
(m>0)
再帰呼び出しを用いれば,シンプルに書ける.
しかしこれらも,whileループのほうが効率がよい.
8
再帰的な定義の例(2)

木構造




トーナメント表の決勝戦から順に見て,
優勝チームの戦績を知る
100万個の記録から,欲しいものを
瞬時に獲得する
ホームディレクトリ以下のすべての
ファイル名を出力する
再帰呼び出しは必要?


するのが自然な場合と,してはいけない
場合がある
呼び出し方よりもデータ構造のほうが重要
9
再帰的な定義の例(3)

文法



BNF記法
• <識別子> ::= <識別子> <英字> |
<識別子> <数字> |
<識別子> '_' |
<英字> | '_'
句構造文法による式の定義
計算機でどう処理する?


字句解析・構文解析を行う.
再帰下降構文解析は,文法と対応した
解析器(パーサ)を生成するが,効率は
必ずしも良くない.
リpp.170-172
a=b++-+c;
↓
字句解析
構文解析
↓
OK
a=b++++c;
↓
字句解析
構文解析
↓
NG
10
次に学ぶこと

ライブラリ関数の活用



(参考)関数の分類


入p.111
先人の知恵を活用する.
勉強・授業のためでなければ,
ライブラリ関数と同じ名前や機能の関数は自作しない.
自作関数: 自分で定義する.⇒ 11月26日のテーマ
ライブラリ関数: 出来合いのもの.printfなど.⇒ ここでの
テーマ
11
ライブラリ


関数・定数・独自型などをまとめて,他のプログラムから利用
できるよう部品化したものを「ライブラリ」という.
ライブラリ関数の分類



標準ライブラリ関数(標準関数,ANSI準拠の関数)
• 情報処理Ⅱで使用するのは,この範囲だけ
POSIX準拠の関数
• 情報ネットワーク演習で使用する
その他(サードパーティライブラリ)
• OpenGL(ビジュアル情報演習で使用する) など
ANSI: American National Standard Institute
POSIX: Portable Operating System Interface for UNIX
リp.346
12
ライブラリ関数とヘッダファイル

既に定義されている関数や定数を利用するには,あらかじめ,
適切なファイル名(ヘッダファイル)を記載しておく.



printf なら #include <stdio.h>
CHAR_BIT なら #include <limits.h>
ライブラリ関数と,記載すべきヘッダファイル名は,オンライン
マニュアルで知ることができる.




man 3 printf
Vine Linuxでおすすめ
jman 3 printf
JM Project (http://www.linux.or.jp/JM/)
ヘッダファイルはコンパイル環境が保有しているが,その所在
は,環境による.
入p.114
リp.369, pp.395-396, p.473, p.421
13
ヘッダファイルとインクルード

ヘッダファイルには,定数,構造体や特殊な型,関数プロトタ
イプなどが宣言されている.




リp.395-396
#include <stdlib.h> とすると,
/usr/include/stdlib.h を取り込む(インクルードする).
慣例として,ファイル名は「.h」で終わらせる.
ヘッダファイルの中で,他のヘッダファイルをインクルードする
こともよく行われる.
ヘッダファイルを自作することもある.そのファイルをインクルー
ドするときは,#include "headerfile.h" のように書く.
14
有用なライブラリ関数(1)

#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
15
有用なライブラリ関数(2)

#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); … 文字列連結
リp.493, p.511
16
有用なライブラリ関数(3)

#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
17
関数名の表記

printf関数,関数printf


printf()関数,関数printf()


この授業で採用している.
関数名であることを明確にする表記法.よく見かける.
printf(3)



「printfというライブラリ関数があって,詳細は,
man 3 printfを実行すれば得られる」の意味.
「(1)」ならコマンド,「(2)」はシステムコール
• man printfを実行すると,ライブラリ関数ではなく,コマ
ンドとしてのprintfの使い方が出てくる.
「printfの実引数に3と書く」ではない.
18
まとめ

再帰呼び出しを用いて関数を定義すると,プログラムがすっ
きり書けることがある.


一般に,再帰を用いないほうが効率的である.


再帰的に定義された問題に適用すると,効果的.
関数内のauto変数は,関数呼び出しごとに生成される.
ライブラリ関数の活用により,先人の知恵を活用しながら,
信頼性の高いソフトウェアが作れる.


関数名,処理内容,ヘッダファイル,引数,戻り値を把握する.
教科書だけでなく,オンラインマニュアルやインターネットの情
報も参考に.
19