第 ９ 章 関 数 の 再 帰 的 定 義 を ル ー ル に す る
１ ． 再 帰 的 定 義 を ル ー ル に す る
再 帰 的 定 義 と は 、 数 列 な ど の 特 定 の 要 素 を 、 そ れ よ り 前 の 要 素 を 用 い て 指 定 す る こ と で あ る 。ETI で は 、 再 帰 的 定 義 か ら 簡 単 に ル ー ル を 作 る こ と が で き る 。 ヘ ッ ド と 同 じ 述 語 が ボ デ ィ に も 含 ま れ て い る ル ー ル を再 帰 ル ー ルと 呼 ぶ 。
２ ． 等 差 数 列 の 和
例 題)
初 項 が ２ 、 公 差 が ２ の 等 差 数 列 の 第 ｎ 項 目 ま で の 和 X を 求 め る プ ロ グ ラ ム を 書 い て 、 第 13項 目 ま で の 和 を 求 め な さ い 。｛ ２ ４ ６ ８ ･･･ ２ ｎ ｝
こ の 等 差 数 列 の ｎ 項 目 ま で の 和 を ｆ(n)と す る と き 、 計 算 式 は 、
= 2 n + f(n－1) ･･･｛ ｎ ≧ １ ｝ ｆ(n)
= 0 ･･･｛ ｎ ＝ ０ ｝
と な る 。 こ の 式 か ら ル ー ル を 作 る こ と を 考 え よ う 。 ま ず 、
ｆ(n) = 2 n + f(n－1) ･･･｛ ｎ ≧ １ ｝
よ り 、 ｆ(n)を 次 の よ う に 求 め る こ と が で き る 。
① *X＝f(n)を 求 め る に は 、
○Ｃ *Ｎ ≧ １ の と き 、
② *Ｎ － １ を 求 め 、*N1 と し 、
③ f(*N1) を 求 め 、*X1 と し 、
④ ２ ×*Ｎ ＋*X1を 求 め 、*X と す る 。
こ れ を も と に 、 次 の ル ー ル は 、 以 下 の よ う に 書 く こ と が で き る 。
(ｆ *N *X) ,{(>= *N 1)} --> (:= *N1 (－ *N 1)),(ｆ *N1 *X1),(:= *X (+ (x 2 *N) *X1)).
① ○Ｃ ② ③ ④
特 に 、 矢 印 以 降 の ② 、 ③ 、 ④ の ア ト ム の 順 序 に 注 意 す る 必 要 が あ る 。 こ の 順 序 で 書 く と 、
*Ｎ → *Ｎ 1→ *Ｘ 1→ *Ｘの 順 に 、 次 々 と 値 が 確 定 し て い く が 、 こ れ 以 外 の 順 序 で は う ま く い か な い 。
ま た 、 ｎ ＝ ０ の と き 、 ル ー ル は 以 下 の よ う に 書 け る 。
(ｆ 0 *X) --> (= *X 0).
① ②
こ の ル ー ル は 次 の 文 と 対 応 し て い る 。
① *X＝f(0)を 求 め る に は 、
② *X＝ ０ と す る 。
こ の ル ー ル で 用 い た ア ト ム と 再 帰 的 定 義 の 部 分 式 と の 対 応 は 以 下 の よ う に な る 。
・ ｎ ≧ １ の と き
(ｆ *N *X) ･･･ ｆ(n) {(>= *N 1)} ･･･ ｛ ｎ ≧ １ ｝ (:= *N1 (－ *N 1)) ･･･ (n－1) (ｆ *N1 *X1) ･･･ f(n－1) (:= *X (+ (x 2 *N) *X1)) ･･･ 2 n + f(n－1)
・ ｎ ＝ ０ の と き
(ｆ 0 *X) ･･･ ｆ(0) (= *X 0) ･･･ 0
以 上 よ り 、 初 項 が ２ 、 公 差 が ２ の 等 差 数 列 の 第 ｎ 項 目 ま で の 和 を 求 め る プ ロ グ ラ ム は 、 ２ つ の ル ー ル で 書 き 表 す こ と が で き る 。以 下 の ル ー ル を 記 述 し 、(ｆ 13 *X) を 実 行 し な さ い 。
(ｆ *N *X),{(>= *N 1)} --> (:= *N1(－ *N 1)), (ｆ *N1 *X1),
(:= *X (+ (x 2 *N) *X1)).
(ｆ 0 *X) --> (= *X 0).
ETIを 起 動 し て 、(f 13 *X)を 入 力 ・ 実 行 す る と 、*Xは 182で あ る こ と が わ か る 。
こ の よ う に 、 漸 化 式 が 与 え ら れ て い る 問 題 を 解 く に は 、 ア ト ム の 順 序 な ど に 注 意 し な が ら 、 漸 化 式 か ら 対 応 す る ル ー ル を 作 れ ば よ い 。
３ ． 階 乗 の 計 算
正 の 整 数 ｎ の 階 乗 を ｎ! と 書 き 、 計 算 式 は 以 下 の よ う に 定 義 さ れ る 。
＝ N ×(N－ １)! … ｛N＞ ０ ｝
＝ １ … ｛ Ｎ ＝ ０ ｝
階 乗 の 計 算 式 を ル ー ル で 表 現 す る 際 、 次 の よ う な 計 算 順 序 が 考 え ら れ る 。
① *X＝ N! を 求 め る に は 、 ○ｃ *N＞０の と き 、
② *Ｎ － １を 求 め 、*N1 と し 、 ③ N1! を 求 め 、*X1 と し 、 ④ *N・ *X1 を 求 め 、*X と す る 。
N！
こ の 計 算 順 序 に 従 っ て 、 ル ー ル を 記 述 す る と 以 下 の よ う に 書 く こ と が で き る 。
(fact *N *X),{(> *N 0)} --> (:= *N1 (－ *N 1)),(fact *N1 *X1),(:= *X (x *N *X1)).
① ○ｃ ② ③ ④
例 題)
上 記 の ル ー ル を 記 述 し 、 ５ の 階 乗 を 求 め る 計 算 を 行 い な さ い 。 そ の と き 、 ど の よ う な 結 果 が 得 ら れ る か ETIで 実 行 し て み な さ い 。
こ の 問 題 を 実 行 す る と 失 敗 す る 。記 述 し た ル ー ル は 、*N が ０ 以 上 の 場 合 だ け 発 火 す る ル ー ル で あ る 。*N＝ ０ に な る と 、条 件 部 を 満 た さ な い た め 、ル ー ル は 適 用 さ れ な い 。す な わ ち 、 適 用 す る ル ー ル が な い の で 失 敗 す る 。そ こ で*N が ０ の と き に 適 用 で き る ル ー ル を 、記 述 し た ル ー ル の 下 に 追 加 す る 。
(fact 0 *X) --> (:= *X 1).
再 帰 ル ー ル で 簡 単 化 が で き な く な っ た と き(こ の 問 題 で は *N＝ ０ に な っ た と き)、こ の ル ー ル が 初 め て 適 用 さ れ 、 再 帰 計 算 を 停 止 さ せ る 。 そ の 後 、 掛 け 算 が 次 々 と 行 わ れ て 求 め る 答 が 得 ら れ る 。
例 題)
先 の 例 題 で 記 述 し た fact の プ ロ グ ラ ム に 、*N=０ の 場 合 の ル ー ル を 追 加 し 、 再 度 ５ の 階 乗 を ETIの デ バ ッ グ モ ー ド で 計 算 し 、 実 行 の 様 子 を 観 察 し な さ い 。
今 度 は*N＝ ０ の 場 合 の 計 算 も 行 わ れ 、答 が120と な っ て 求 ま る 。こ の よ う に 再 帰 ル ー ル は 、 再 帰 計 算 を 停 止 さ せ る ル ー ル と 対 に な っ て 、 問 題 の 答 を 求 め る 。 停 止 さ せ る ル ー ル が 無 い と 、 無 限 計 算 に 陥 る 。
４ ． フ ィ ボ ナ ッ チ 数 列
フ ィ ボ ナ ッ チ 数 列 を 理 解 す る た め に 、 次 の よ う な 問 題 を 考 え て み よ う 。 例 え ば 、 １ つ が い の ウ サ ギ は 、 毎 月 １ つ が い の 子 を 産 む 。 そ の 子 は 生 ま れ て ２ ヵ 月 経 過 す る と 子 を 産 み 始 め る 。 よ っ て 、 最 初 に １ つ が い の 子 が い た と す る と 、 １ ヶ 月 目 と ２ ヶ 月 目 は 子 を 産 ま ず 、 ３ ヶ 月 目 に な っ て 子 を 産 む よ う に な る 。 そ し て 、 ３ ヶ 月 目 以 降 は 、 毎 月 １ つ が い ず つ 子 を 産 む 。 月 日 を 重 ね て い く と 、 ウ サ ギ は ど の よ う に 増 え て い く だ ろ う か 。
図 を み る と 、Ｎ ヶ 月 目 の ウ サ ギ の 数 は 、前 月(Ｎ － １)の 数 と 前 々 月(Ｎ － ２)の 数 を 合 わ せ た 数 に な る 。 こ の よ う に 、 フ ィ ボ ナ ッ チ 数 列 と は 、 第 Ｎ 項 の 数 が 、 第(Ｎ － １)項 と 、 第(Ｎ
－ ２)項 の 数 の 和 で あ る 数 列 で あ る 。た だ し 、第 ０ 項 は ０ 、第 １ 項 は １ で あ る 。こ れ を 漸 化 式 で 表 す と 以 下 の よ う に な る 。
fib(N)
= fib(N－1) + fib(N－2) … {N≧ ２}
= 0 … ｛N＝ ０ ｝
= 1 … ｛N＝ １ ｝
５ ． ア ッ カ ー マ ン 関 数
ア ッ カ ー マ ン 関 数 は 、 以 下 の 式 で 定 義 さ れ る 関 数 で あ り 、 ２ つ の 引 数 ｘ 、 ｙ に 与 え る 数 が 大 き く な る と 、 再 帰 計 算 の 回 数 が 爆 発 的 に 増 え る こ と で 知 ら れ て い る 。 こ の た め 、 コ ン パ イ ラ の 性 能 を 調 べ る こ と な ど に も 使 う こ と が で き る 。 し か し な が ら 、 こ の 関 数 は 具 体 的 な 意 味 を 持 っ て 何 か を 計 算 す る 式 と し て 作 ら れ て い る わ け で は な い 。
ack(0 , y) = y +1
ack(x , 0) = ack (x－1 , 1) … ｛ ｘ ≠ ０ ｝
ack(x , y) = ack (x－1 , ack(x , y－1)) … ｛ ｘ ≠ ０, ｙ ≠ ０ ｝
再 帰 に よ っ て 計 算 が 爆 発 的 に 増 加 し て い る 様 子 を 下 の 表 に 示 す 。例 え ば 、*X＝ ３ 、*Y＝ ７ の と き で 、約 70万 回 の 再 帰 計 算 が 起 こ り 、ETIで 実 行 す る と 約 40秒 の 計 算 時 間 を 要 す る 。
(X , Y) 値 再 帰 計 算 回 数
(0 , 0) 1 1
(0 , 1) 2 1
(1 , 1) 3 4
(2 , 1) 5 14
(2 , 2) 7 27
(3 , 1) 13 106 (3 , 2) 29 541 (3 , 3) 61 2432 (3 , 4) 125 10307 (3 , 5) 253 42438 (3 , 6) 509 172233 (3 , 7) 1021 693964
