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