データ構造とアルゴリズム論第７章再帰処理平成27年6月26日森田彦理解度チェック1（問題１）空欄①に入るのは次のいずれですか？適切なものを選択して下さい。１．i ５．10 ２． No ３． 0 ４．9 理解度チェック1 解答空欄①に入るのは次のいずれですか？適切なものを選択して下さい。１．i ２． No ３． 0 ４．9 ５． 10  ”番兵”を入れるのは、最後の要素の一つ後ろ。  今の場合、A[9]の後ろだから、10になる。理解度チェック2（問題2）空欄②に入る適切な式は次のいずれですか？１．i≧0 ４．i≦40 ２． i≧1 ５． i≦41 ３． i≦No 理解度チェック2 解答空欄②に入る適切な式は次のいずれですか？１．i≧0 ４．i≦40 ２． i≧1 ５． i≦41 ３． i≦No  番兵法の場合、求めるデータが見つかった場所（位置）が元々の配列の範囲内かどうかが問題。  今の場合、元々の配列要素はA[40]まである。  見つかった位置ｉがi≦40であれば、データを見つけたことになる。理解度チェック3（問題3）空欄③に入る適切な式は次のいずれですか？１．No<A[Mid] ３．No>A[Mid] ２． No=A[Mid] ４．No≠A[Mid] 理解度チェック3 解答空欄③に入る適切な式は次のいずれですか？１．No<A[Mid] ３．No>A[Mid] Low Mid ・・・ A Low A ２． No=A[Mid] ４． No≠A[Mid] High ・・・ High ・・・・・・  ③の条件が成り立てば、探索範囲が左半分に。  今は昇順にソートしている。  NoはA[Mid]より小さい。理解度チェック4（問題4）空欄④に入る適切な式は次のいずれですか？１．No<A[Mid] ３．No>A[Mid] ２． No=A[Mid] ４．No≠A[Mid] 理解度チェック4 解答空欄④に入る適切な式は次のいずれですか？１．No<A[Mid] ３．No>A[Mid] Low Mid ・・・ A Low A ２． No=A[Mid] ４． No≠A[Mid] High ・・・ High ・・・・・・  ③の条件が成り立てば、探索範囲が左半分に。  今は降順にソートしている。  NoはA[Mid]より大きい。再帰とは？  自身の定義（の一部）に自身を含むこと。  日常的な例鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く  プログラムの世界ではメソッドの再帰的呼び出し、あるいはデータ構造の再帰的定義に用いられる。本章（本日）の学習のねらい ① メソッドの再帰的定義（呼び出し）の例を学習する。→“再帰”の概念を理解する。 ② 再帰処理の応用例としてフラクタル図形の描画を学習する。 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≧2 nの入力 Ans ←Fact(n) No Yes X ←n*Fact(n-1) Ansの表示 Xの値を返す終了戻る X ←1 終了条件が必要！メソッド呼び出しの連鎖→p.118参照プログラムの作成→【基礎課題7-1 】(p.119) 【基礎課題7-2】－コラッツの予想コラッツ（Collatz）の予想 ある数字が偶数なら２で割る 奇数なら3倍して1を加えるという操作を繰り返すと必ず１になる。例：５→１６→８→４→２→１＜課題の内容＞コラッツの操作を再帰的に繰り返すことで、上の予想を実際に確かめるプログラムを作成する。 7-2 再帰処理の応用フラクタル図形どの一部をとっても全体と同じパターン（形）になっている図形 コッホ（Koch）曲線→【応用課題7-A】 (p.125) 植物(!?) → 【応用課題7-B】(p.131) 今後の予定  6/26  7/ 3  7/10  7/17  7/24 第７章再帰処理第８章連結リスト第９章木構造第１０章スタックとキュー第２回テスト & 課題最終チェックプリントをどれだけじっくり読んで理解しているかがポイント→理解度確認テストでチェック学習に当たって  第7章までの基礎課題を全て終了した学生は、7章の応用課題を終了すれば演習を終えても結構です。  来週以降に未提出の基礎課題を持ち越すと、挽回が困難になります。鏡の中の鏡ずっと際限なく鏡の列が続く。「鏡に映す」という操作の再帰的呼び出しの例