データ構造とアルゴリズム論
第8章 再帰処理
平成15年12月2日
森田 彦
基礎課題提出状況(11/25)
平均提出数=36.8 (全課題数41)
基礎課題提出状況(11/25)
平均提出数=36.8
70
60
度数(人数)
50
40
30
このままでは危険!
20
10
0
0~20
21~25
26~30
31~35
36~40
41
提出数範囲
66.7%が36題以上を提出
応用課題提出状況(11/25)
平均提出課題数=8.7
応用課題提出状況(11/25)
平均提出数=8.7
40
35
度数(人数)
30
25
20
15
10
5
0
0
1~4
5~8
9~12
13~16
提出数範囲
13題以上提出は約27%
17~20
21~26
再帰とは?
 自身の定義(の一部)に自身を含むこと。
 日常的な例
鏡を持って鏡に向かった場合→鏡の中に
鏡が映る・・・鏡の列が続く
 プログラムの世界では
メソッドの再帰的呼び出し、あるいはデー
タ構造の再帰的定義に用いられる。
本章(本日)の学習のねらい
① メソッドの再帰的定義(呼び出し)の例を
学習する。→“再帰”の概念を理解する。
② 再帰処理の応用例としてフラクタル図形
の描画を学習する。
8-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.126参照
プログラムの作成→【基礎課題8-1 】
【基礎課題8-2】-コラッツの予想
コラッツ(Collatz)の予想
ある数字が偶数なら2で割る
奇数なら3倍して1を加える
という操作を繰り返すと必ず1になる。
例:5→16→8→4→2→1
<課題の内容>
コラッツの操作を再帰的に繰り返すことで、上の
予想を実際に確かめるプログラムを作成する。
8-2 再帰処理の応用
フラクタル図形
どの一部をとっても全体と同じパターン(形)に
なっている図形
コッホ(Koch)曲線→【応用課題8-A】
植物(!?) → 【応用課題8-B】
第2回目テストのアナウンス
 日時:12/9 13:15~14:15 (13:10までに
着席しておいて下さい)
 実施形態:ペーパーテスト形式(テスト中
はPCを使用できません)
 参照等:テキスト、プリント、自作ノート参
照可
 出題範囲:第5章~第7章まで
 アドバイス:暗記ではなく、処理の流れを
“理解する”事に重点を置いて下さい。
テスト準備のポイント
 問題1 レコード構造-クラスの利用
クラスの定義・利用の仕方をよく理解しておくこ
と→【基礎課題5-1】、【基礎課題5-2】を(暗記で
はなく)を自分の頭で作成できるようにしておい
て下さい。
 問題2 ソートのアルゴリズム
バブルソート、選択ソート、挿入ソートの処理の
流れをトレースしておくこと→p.88~89、p.96~
97、p.100~101を(自分で手を動かして)良く確
認しておいて下さい。
テスト準備のポイント
 問題3 探索のアルゴリズム
線形探索(番兵法)と2分探索のアルゴ
リズム(流れ図)をよく理解しておくこと
(p.107,p.108~109,p.115)→具体的な
データを用いて、処理の流れをトレースし
ておいて下さい。
1両日中にHPにより詳細な情報を掲載します。
参考にして下さい。
鏡の中の鏡
ずっと際限なく鏡
の列が続く。
「鏡に映す」という
操作の再帰的呼
び出しの例
ダウンロード

スライド