データ構造とアルゴリズム論第７章再帰処理平成17年12月6日森田彦基礎課題提出状況(11/29) 基礎課題提出状況（11/29）　平均=33.3（昨年32.7）　［全課題37題］ 90 54 % が全課 '04年度 '05年度題を提出 80 70 度数（人数） 60 50 40 30 17名（12.5%）このままでは危険! 20 10 0 6～20 21～25 昨年とほぼ同じペース 26～30 提出数 31～35 36～37 58.8%が36題以上を提出応用課題提出状況（11/29）度数（人数）応用課題提出状況（11/29）　平均13.93（昨年13.5）全課題25題全課題提 '04年度出 '05年度は５名 50 45 40 35 30 25 20 15 10 5 0 0 1～5 6～10 11～15 16～20 21～25 提出数昨年より若干多い！ 13題以上提出は約61% 再帰とは？  自身の定義（の一部）に自身を含むこと。  日常的な例鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く  プログラムの世界ではメソッドの再帰的呼び出し、あるいはデータ構造の再帰的定義に用いられる。本章（本日）の学習のねらい ① メソッドの再帰的定義（呼び出し）の例を学習する。→“再帰”の概念を理解する。 ② 再帰処理の応用例としてフラクタル図形の描画を学習する。 7-1 再帰処理例：階乗の計算 5!=5×4×3×2×1 一般的には・・・ n!=n×(n-1)×(n-2)×･･･×2×1 これを書き直すと・・・ n!=n×(n-1)! → 再帰的定義プログラムで表現するためにn!を計算するメソッドFact(n)を定義 → Fact(n)=n×Fact(n-1) 階乗：factorial n!の計算（メソッドの再帰的定義による） Fact(n) 開始 nの入力メソッドの呼び出し Ans ←Fact(n) Ansの表示終了値を返す n≧2 No Yes X ←n*Fact(n-1) X ←1 Xの値を返す戻る終了条件が必要！メソッド呼び出しの連鎖→p.112参照プログラムの作成→【基礎課題7-1 】(p.113) 【基礎課題7-2】－コラッツの予想コラッツ（Collatz）の予想 ある数字が偶数なら２で割る 奇数なら3倍して1を加えるという操作を繰り返すと必ず１になる。例：５→１６→８→４→２→１＜課題の内容＞コラッツの操作を再帰的に繰り返すことで、上の予想を実際に確かめるプログラムを作成する。 7-2 再帰処理の応用フラクタル図形どの一部をとっても全体と同じパターン（形）になっている図形 コッホ（Koch）曲線→【応用課題7-A】 (p.119) 植物(!?) → 【応用課題7-B】(p.123) 今後の予定  12/6 第７章再帰処理  12/13 第８章連結リスト  12/20 第９章木構造  12/27 第２回目テスト(13:15～14:15) ★範囲は第９章まで ★実施要領は第１回目と同様 ★プリントをどれだけじっくり読んで理解しているかがポイント  1/10 終章補足＆課題最終チェック欠席回数が3回以上の人は出席率に注意して下さい。鏡の中の鏡ずっと際限なく鏡の列が続く。「鏡に映す」という操作の再帰的呼び出しの例