再帰的計算とフラクタル

計算機演習A,B 2021年7月26日 担当教員: 劉 雪峰

再帰的作業の例

教室の授業で資料を配布するとき、以下のやり方がよく使用されます。

「自分の資料を取って、残りを後ろの方に渡してください。」という指示によって、資料を一番前にいる学生に渡せば、資料を全員に届けることができます。

この例では、以下の特徴があります。

作業の終了条件は、

再帰的計算の例

$n$の階乗の計算$F(n)$を考えます。$n$の階乗は「$n-1$の階乗」と「$n$」との積ですので、以下の再帰的計算によって$n$の階乗を算出することができます。

特徴: 関数が関数自身を呼び出します。

上記の階乗の例では、$F(n)$は$F$自身を呼び出して$F(n-1)$の値を計算してから、$F(n-1)$と$n$の積を返します。コードはシンプルであるという特徴があります。

演習1

再帰的計算により、$1$から$n$までの各整数の平方の和を計算する$S(n)$を作成してください。

$$S(n) = 1+2^2+3^2+\cdots + n^2$$

再帰的計算によるフラクタルの描画

コッホ曲線(Koch curve)の例を再検討します。

コッホ曲線の作業(関数 draw_koch の作成)

draw_kochは一層ずつ呼ばれますが、毎回の計算では、残りの計算回数(再帰的計算の回数)nが1ずつ減ります。

終了条件として、

線分を用意して、関数draw_kochを呼び出します。

注意:draw_kochの中の再帰的計算の回数nを大きい値にすると、計算時間が長くなります。5以下の値を使ってください。

ツリーの描画

関数名:draw_tree(line, times)

作成方法

終了条件

フラクタルを使って、家を飾ってみます。

注意:

上記の2つの例にある「残りの再帰的計算の回数n」の役割を理解してください。

レポート課題

フラクタルを自分で設計して、作成してください。また、フラクタルを使って、以前のレポートで作成した家を飾ってください。

ヒント:Googleの画像検索の中で「フラクタル 木」の例を参考にしてください。