データ構造とアルゴリズム論 第８章 再帰処理 平成15年12月2日 森田 彦
基礎課題提出状況(11/25) 平均提出数=36.8 (全課題数41) このままでは危険! 66.7%が36題以上を提出
応用課題提出状況（11/25） 平均提出課題数＝8.7 13題以上提出は約27%
再帰とは？ 自身の定義（の一部）に自身を含むこと。 日常的な例 鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く 鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く プログラムの世界では メソッドの再帰的呼び出し、あるいはデータ構造の再帰的定義に用いられる。
本章（本日）の学習のねらい メソッドの再帰的定義（呼び出し）の例を学習する。→“再帰”の概念を理解する。 再帰処理の応用例としてフラクタル図形の描画を学習する。
8-1 再帰処理 例：階乗の計算 5!=5×4×3×2×1 一般的には・・・ n!=n×(n-1)×(n-2)×･･･×2×1 8-1 再帰処理 例：階乗の計算 5!=5×4×3×2×1 一般的には・・・ n!=n×(n-1)×(n-2)×･･･×2×1 これを書き直すと・・・ n!=n×(n-1)! → 再帰的定義 プログラムで表現するためにn!を計算するメソッドFact(n)を定義 階乗：factorial → Fact(n)=n×Fact(n-1)
n!の計算（関数の再帰的定義による） 終了条件が必要！ 関数呼び出しの連鎖→p.126参照 プログラムの作成→【基礎課題8-1 】 Fact(n) n≧2 X ←n*Fact(n-1) Xの値を返す 戻る X ←1 No Yes 開始 nの入力 Ans ←Fact(n) Ansの表示 終了 メソッドの呼び出し 値を返す 終了条件が必要！ 関数呼び出しの連鎖→p.126参照 プログラムの作成→【基礎課題8-1 】
【基礎課題8-2】－コラッツの予想 コラッツ（Collatz）の予想 ある数字が偶数なら２で割る 奇数なら3倍して1を加える という操作を繰り返すと必ず１になる。 例：５→１６→８→４→２→１ ＜課題の内容＞ コラッツの操作を再帰的に繰り返すことで、上の予想を実際に確かめるプログラムを作成する。
8-2 再帰処理の応用 フラクタル図形 どの一部をとっても全体と同じパターン（形）になっている図形 8-2 再帰処理の応用 フラクタル図形 どの一部をとっても全体と同じパターン（形）になっている図形 コッホ（Koch）曲線→【応用課題8-A】 植物(!?) → 【応用課題8-B】
第２回目テストのアナウンス 日時：12/9 13:15～14:15 （13:10までに着席しておいて下さい） 日時：12/9 13:15～14:15 （13:10までに着席しておいて下さい） 実施形態：ペーパーテスト形式（テスト中はＰＣを使用できません） 参照等：テキスト、プリント、自作ノート参照可 出題範囲：第５章～第７章まで アドバイス：暗記ではなく、処理の流れを“理解する”事に重点を置いて下さい。
テスト準備のポイント 問題１ レコード構造－クラスの利用 問題１ レコード構造－クラスの利用 クラスの定義・利用の仕方をよく理解しておくこと→【基礎課題5-1】、【基礎課題5-2】を（暗記ではなく）を自分の頭で作成できるようにしておいて下さい。 問題２ ソートのアルゴリズム バブルソート、選択ソート、挿入ソートの処理の流れをトレースしておくこと→p.88～89、p.96～97、p.100～101を（自分で手を動かして）良く確認しておいて下さい。
テスト準備のポイント 問題３ 探索のアルゴリズム 問題３ 探索のアルゴリズム 線形探索（番兵法）と２分探索のアルゴリズム（流れ図）をよく理解しておくこと（p.107,p.108～109,p.115）→具体的なデータを用いて、処理の流れをトレースしておいて下さい。 １両日中にHPにより詳細な情報を掲載します。参考にして下さい。
鏡の中の鏡 ずっと際限なく鏡の列が続く。 「鏡に映す」という操作の再帰的呼び出しの例