前回
	「関数」の復習をした
		その中で再帰も復習
			当初は、「関数」＝「命令列に名前を付ける」
			再帰を考えると、「再帰関数」は、「複数（原理的には無限）」の長さの命令に相当する
				「『可変長』の命令列」に名前をつける
					自由な形ではなくて、「『同じ命令』の繰り返し」の形

			再帰プログラムの基本構造
				関数名(制御変数) {
					if ( 制御変数が最低値かどうか ) {
						なにもしない
					} else {
						「何か」一つして(繰り返す命令)
						関数名 (制御変数の値を小さくする)	再帰呼び出し
					}
				}
				
				この再帰的関数は、「何か」を繰り返す関数になっている

		値を返す事ができる
			return 命令
		引数に型が指定できる
			! 最初は「文字列」だけだったので「char *」がおまじない
			仮引数変数の前には「その変数が保持するデータの型」を書く
				整数値の引数の場合は int
				文字の引数の場合は char
				「文字列」の引数の場合は char *
			とそれぞれ型名を記述する
				関数の型も同じ

	三つの基本的な制御構造
		順接
			二つの命令 P, Q から関数 f() を作る
				f() {
					P;Q; ( P をやってから、 Q を行う )
				}
					# P;Q; と Q;P; は異なる

		条件分岐
			二つの命令 P, Q と条件 C(x) からから関数 f(x) を作る
				f(x) {
					if ( C(x) ) {	条件が成立したとき
						P;
					} else {		不成立の場合は
						Q;
					}
				}
					もし C(x) が成立したら P, そうでなければ Q を実行
						条件 C によって P と Q どちらか一方を実行

		再帰
			制御変数 x と、最低値を判定する C(x),と、
			値を小さくする φ(x) ( φ(x)は x をより小さくし、
				これを繰り返し適用すると、いつかは C(x) が成立する)			
			繰り返す命令 P があったとき
				f(x) {
					if ( C(x) )	{	最低値
						なにもしない
					} else {
						P;
						f(φ(x));		再帰呼び出し
										引数に関数φを適用する事によい
										引数の値が「小さく」なる
					}
				}


	前回の課題の 2
		階乗の計算をする
			factrial(int n) :	n が自然数の時に n! を計算
				# n = 0, 1, 2,... とし「0! = 1」と決める

									1					(n=0 の時)
				fcatrial(n) = {
									n * fcatrial(n-1)	(n>0 の時)

					# 計算機(C 言語）では、「再帰的定義」
					# 数学では、「帰納的定義」

	int factrial(int n) {
		if ( n <= 0 ) {		/* なぜ == でなく <= かというと安全性を取った */
			return 1;		/* n <= 0 の時は n! = 1 とする */
		} else {
			return n * factrial ( n - 1 );
		}
		/* ここにくることはない */
	}

	この問題のポイント
		作成したい「階乗の関数」が、最初から「帰納的」に定義されている
			そのまま、「再帰」で実現できる
			/* 数学証明表現は機械的にその問題を解くプログラムにできる */
			/* 二次方程式の解の存在証明を読むと、実は、解の公式が導出できる
				解の公式＝解を求めるプログラム(アルゴリズム)
				と考えてよい */

		もし、作りたい関数が、帰納的に定義されていなかったら ?
			-> 帰納的に定義しなおす必要がある
				<= これは、関数の値の存在証明とほぼ同じ
					-> 数学の人間は、問題を「証明」で解く事により、プログラムが作れる

		再帰の考え方 : 帰納法の考え方
			全体を、一つと残り(残りも全体と同じ構造を持つ)に分ける

ユークリッドの互除法
	a,b : 自然数 ( 0 以上の整数 )
		の最大公約数を (a,b) で表現する事にする

	[R.1]	(a,0) = a
	[R.2]	(a,b) = (b,r)	# r は a を b で割ったときの余り

	上記の性質を利用すると、最大公約数を求める手続き
	
	0.(a,b) を求めたい ( a, b >= 0 )
	1.もし、b が 0 なら答えは a である (R.1) ので
		a を答えとして終了
	2. そうでなければ、a を b で割ったあまり(r とする)を求め、
		(b,r) を求めればよい (R.2:帰納的)

					a				(b=0 の時)
	gcm(a,b) = {
					gcm(b,a%b)		(b>0 の時)
						# a%b : a を b で割った余り

	C 言語の関数としては、帰納法で実現可能

		int gcm(int a, int b) {
			if ( b == 0 ) {
				return a;
			} else {
				return gcm(b,a%b);
					/*
							a>b の時に、 b と a%b
							a<b の時は、 a と b%a
						とあるが、プログラムでは ??
							常に、b と a%b だけど大丈夫 ??
								a>b の時は、もちろん、 a と a%b で OK
								a<b の時は、どうなるか ?
									b と a%b
									b と a
									再度 gcm を呼び出すと
										a と b%a ( a>b が保証されている )

						gcm(12,16)
							-> gcm(16,12%16)
							-> gcm(16,12)
							-> gcm(12,16%12)
							-> gcm(12,4)
							-> gcm(4,12%4)
							-> gcm(4,0)
							-> 4
					*/
			}
		}

	gcm(a,b) -> gcm(b,a%b)
		a>b の時 a%b は、b より小さくなる
			a,b の小さい方を取ると、
				a,b の場合 b
				b,a%b の場合は a%b
					「小さく」なる
		a<b の時
			a, b%a (gcm が二度呼ばれた後に)
				a,b の小さいほうは a
				a, b%a の小さいは b%a
					「小さく」なる


[副作用]
	入出力を伴う関数は、「副作用」をもっている
		純粋な関数とはいえない
			特に入力に関しては、入力関数を呼び出すたびに、プログラムは
				入力待ちになり、そのたびに「データの入力を促す」事になる

	もし、入力結果を再度利用したい場合はどうするか ?
		入力関数を二度呼び出すと、二度入力作業が必要になり、
			(同じ値をしていないと..) 異なった値になる
				「入力値を二度利用する場合」は、「入力関数を二度呼んではいけない」
					同じ値を、何度も利用する場合 : 変数を利用する
						変数に値が設定されていれば、同じ変数を利用する事により、同じ値を何度も参照可能
							ところが、「変数を利用するには関数を作る必要がある」
								なので、入力値は、関数の引数に与える事になる

[乱数]
	rand()	ライブラリ関数
		乱数値を返す関数
			呼び出すたびに、(一般には..)異なる値を返す
				その値は(一応..)予想できない(事になっている)

	数当てゲーム
		一方が、一定の範囲(例 : 1 から 100)の数を決める
		他方が、それを予想する
			予想値を相手に伝える
				あっていれば、「あたり」いう
				あってなければ、「おきいかちいさいか」を答える
					さらに、予想を続ける