データ構造とアルゴリズム論 第７章 再帰処理 平成16年11月30日 森田 彦
基礎課題提出状況(11/16) 平均提出数=32.7 (全課題数37) 56%が全課題を提出 21名（15.6%） このままでは危険! 平均提出数=32.7 (全課題数37) 56%が全課題を提出 21名（15.6%） このままでは危険! 62.2%が36題以上を提出
応用課題提出状況（11/16） 平均提出課題数＝13.5 ／ 25 全課題提出は３名 13題以上提出は約63%
再帰とは？ 自身の定義（の一部）に自身を含むこと。 日常的な例 鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く 鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く プログラムの世界では メソッドの再帰的呼び出し、あるいはデータ構造の再帰的定義に用いられる。
本章（本日）の学習のねらい メソッドの再帰的定義（呼び出し）の例を学習する。→“再帰”の概念を理解する。 再帰処理の応用例としてフラクタル図形の描画を学習する。
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)
今後の予定 11/30 第７章 再帰処理 12/7 第８章 連結リスト 12/14 第２回目テスト(13:15～14:15) 11/30 第７章 再帰処理 12/7 第８章 連結リスト 12/14 第２回目テスト(13:15～14:15) ★範囲は８章まで ★実施要領は第１回目と同様 12/21 第９章 木構造（応用課題のみ） 1/11 今後の（プログラミング関連）学習ガイダンス ＆ 課題チェック 基礎課題未了で途中退出した学生は早退とみまします。
鏡の中の鏡 ずっと際限なく鏡の列が続く。 「鏡に映す」という操作の再帰的呼び出しの例