データ構造とアルゴリズム論 第７章　再帰処理 平成16年11月30日 森田　彦.

Presentation on theme: "データ構造とアルゴリズム論 第７章　再帰処理 平成16年11月30日 森田　彦."— Presentation transcript:

1 データ構造とアルゴリズム論 第７章　再帰処理 平成16年11月30日 森田　彦

2 基礎課題提出状況(11/16) 平均提出数=32.7 (全課題数37) 56%が全課題を提出 21名（15.6%） このままでは危険!
平均提出数=32.7　(全課題数37) 56%が全課題を提出 21名（15.6%） このままでは危険! 62.2%が36題以上を提出

3 応用課題提出状況（11/16） 平均提出課題数＝13.5　／ 25 全課題提出は３名 13題以上提出は約63%

4 再帰とは？ 自身の定義（の一部）に自身を含むこと。 日常的な例 鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く
　鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く プログラムの世界では 　メソッドの再帰的呼び出し、あるいはデータ構造の再帰的定義に用いられる。

5 本章（本日）の学習のねらい メソッドの再帰的定義（呼び出し）の例を学習する。→“再帰”の概念を理解する。
再帰処理の応用例としてフラクタル図形の描画を学習する。

6 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)

7 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)

8 【基礎課題7-2】－コラッツの予想 コラッツ（Collatz）の予想 ある数字が偶数なら２で割る 奇数なら3倍して1を加える
という操作を繰り返すと必ず１になる。 例：５→１６→８→４→２→１ ＜課題の内容＞ 　コラッツの操作を再帰的に繰り返すことで、上の予想を実際に確かめるプログラムを作成する。

9 7-2 再帰処理の応用 フラクタル図形 どの一部をとっても全体と同じパターン（形）になっている図形
7-2　再帰処理の応用 フラクタル図形 　どの一部をとっても全体と同じパターン（形）になっている図形 コッホ（Koch）曲線→【応用課題7-A】 (p.119) 植物(!?)　→　【応用課題7-B】(p.123)

10 今後の予定 11/30 第７章 再帰処理 12/7 第８章 連結リスト 12/14 第２回目テスト(13:15～14:15)
11/30　第７章　再帰処理 12/7 第８章　連結リスト 12/14　第２回目テスト(13:15～14:15) 　　　　　★範囲は８章まで 　　　　　★実施要領は第１回目と同様 12/21 第９章　木構造（応用課題のみ） 1/11　今後の（プログラミング関連）学習ガイダンス　＆　課題チェック 基礎課題未了で途中退出した学生は早退とみまします。

11 鏡の中の鏡 ずっと際限なく鏡の列が続く。 「鏡に映す」という操作の再帰的呼び出しの例