再帰的計算とフラクタルの作成

再帰的作業の例

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

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

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

  • 「資料を取って、残りを後ろの方に渡す」という作業(関数と考える)が繰り返し行われます。
  • 授業の教員として、最初に一回の作業(関数の実行)で済みです。
  • 作業の終了条件として、「資料がなくなる」こと、または、「資料を受けった生徒の後に他の生徒がいないこと」です。

再帰的な計算の例

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

  • $F(n) = n*F(n-1)$ (関数自身を呼び出す)
  • $n=0$ のとき、$F(0)=1$  (終了条件)
In [2]:
function value = F(n)
  if n==0 
    value = 1;
  else
    value = n*F(n-1);
  end
end
In [7]:
F(6)
ans =  720

上記の階乗の例では、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$$
In [26]:
function value=S(n)
  if n==0 
  ??
  else
  ??
  end
end

フラクタルを再帰的計算で描画

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

コッホ曲線の作業(関数 Draw_Koch)を定義します。

  • 与えられる線分について、3等分を取って、真ん中の線分を「山」にして、合わせて4つの線分を作成する。
  • 各線分に対して、Draw_Kochを呼び出し、引数としてこの関数に渡す。

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

終了条件として、

  • 残り回数が$0$になれば、(3等分の作業をしないまま)線分を描画して、終了します。
In [16]:
function draw_koch(line, n)
    if n == 0
        plot(line(:,1), line(:,2), 'r-')
    else
        %3等分を取る
        p1=line(1,1:2);
        p2=line(2,1:2);
        p3 = 2/3*p1+1/3*p2;
        p4 = 1/3*p1+2/3*p2;
        
        %「山」にするための新しい節点を計算する
        theta=pi/3;
        A=[cos(theta), -sin(theta); sin(theta), cos(theta)];
        new_point = (A*(p4'-p3'))' + p3;

        %4つの線分を処理する
        draw_koch( [p1; p3], n-1);
        draw_koch( [p4; p2], n-1);
        draw_koch( [p3; new_point], n-1);  
        draw_koch( [new_point; p4], n-1);  
    end
end

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

注意:draw_kochの中の最大深さNを大きい値にすると、計算時間が長くなります。

In [17]:
hold on
draw_koch([0,0;1,0],3)
axis("equal")
Gnuplot Produced by GNUPLOT 5.0 patchlevel 3 -0.2 -0.1 0 0.1 0.2 0.3 0.4 0.5 0 0.2 0.4 0.6 0.8 1 gnuplot_plot_1a gnuplot_plot_2a gnuplot_plot_3a gnuplot_plot_4a gnuplot_plot_5a gnuplot_plot_6a gnuplot_plot_7a gnuplot_plot_8a gnuplot_plot_9a gnuplot_plot_10a gnuplot_plot_11a gnuplot_plot_12a gnuplot_plot_13a gnuplot_plot_14a gnuplot_plot_15a gnuplot_plot_16a gnuplot_plot_17a gnuplot_plot_18a gnuplot_plot_19a gnuplot_plot_20a gnuplot_plot_21a gnuplot_plot_22a gnuplot_plot_23a gnuplot_plot_24a gnuplot_plot_25a gnuplot_plot_26a gnuplot_plot_27a gnuplot_plot_28a gnuplot_plot_29a gnuplot_plot_30a gnuplot_plot_31a gnuplot_plot_32a gnuplot_plot_33a gnuplot_plot_34a gnuplot_plot_35a gnuplot_plot_36a gnuplot_plot_37a gnuplot_plot_38a gnuplot_plot_39a gnuplot_plot_40a gnuplot_plot_41a gnuplot_plot_42a gnuplot_plot_43a gnuplot_plot_44a gnuplot_plot_45a gnuplot_plot_46a gnuplot_plot_47a gnuplot_plot_48a gnuplot_plot_49a gnuplot_plot_50a gnuplot_plot_51a gnuplot_plot_52a gnuplot_plot_53a gnuplot_plot_54a gnuplot_plot_55a gnuplot_plot_56a gnuplot_plot_57a gnuplot_plot_58a gnuplot_plot_59a gnuplot_plot_60a gnuplot_plot_61a gnuplot_plot_62a gnuplot_plot_63a gnuplot_plot_64a

ツリーの描画

関数名: draw_tree(line, times)

作成方法

  • 与えられる線分を3等分を取ります。
  • 3等分の節点を順番にp1,p2,p3,p4として、p2とp3のところで、線分との角が30度となる「枝」を線分の両側で作成する。
  • 2つの枝を含めて5つの線分をdraw_treeで処理します

終了条件

  • 残りの再帰的計算の回数$n$が0になるとき、関数に与えられる線分を描きます。
![http://www.ces-alpha.org/download/gs/?label=F21&conf_id=CM2019&verify=faede](attachment:fractal_tree.svg)
In [20]:
function draw_tree(line, n )
     
    if n == 0
       plot(line(:,1), line(:,2), 'r-')    
    else
        %3等分を取る
        p1=line(1,1:2);
        p4=line(2,1:2);
        p2 = 2/3*p1+1/3*p4;
        p3 = 1/3*p1+2/3*p4;
        
        %「枝」にするための新しい節点を計算する(左側)
        theta=pi/6;
        A=[cos(theta), -sin(theta); sin(theta), cos(theta)];
        new_point_1 = (A*(p3'-p2'))' + p2;

        %「枝」にするための新しい節点を計算する(右側)
        theta=-pi/6;
        A=[cos(theta), -sin(theta); sin(theta), cos(theta)];
        new_point_2 = (A*(p4'-p3'))' + p3;

        draw_tree( [p1; p2], n-1);
        draw_tree( [p2; p3], n-1);
        draw_tree( [p3; p4], n-1);
        %「枝」を処理する
        draw_tree( [p2; new_point_1], n-1);
        draw_tree( [p3; new_point_2], n-1);
    end

end
In [19]:
hold on
draw_tree([0,0;0,1],1)
axis("equal")
Gnuplot Produced by GNUPLOT 5.0 patchlevel 3 0 0.2 0.4 0.6 0.8 1 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 gnuplot_plot_1a gnuplot_plot_2a gnuplot_plot_3a gnuplot_plot_4a gnuplot_plot_5a
In [8]:
hold on
draw_tree([0,0;0,1],4)
axis("equal")
Gnuplot Produced by GNUPLOT 5.0 patchlevel 3 0 0.2 0.4 0.6 0.8 1 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 gnuplot_plot_1a gnuplot_plot_2a gnuplot_plot_3a gnuplot_plot_4a gnuplot_plot_5a gnuplot_plot_6a gnuplot_plot_7a gnuplot_plot_8a gnuplot_plot_9a gnuplot_plot_10a gnuplot_plot_11a gnuplot_plot_12a gnuplot_plot_13a gnuplot_plot_14a gnuplot_plot_15a gnuplot_plot_16a gnuplot_plot_17a gnuplot_plot_18a gnuplot_plot_19a gnuplot_plot_20a gnuplot_plot_21a gnuplot_plot_22a gnuplot_plot_23a gnuplot_plot_24a gnuplot_plot_25a gnuplot_plot_26a gnuplot_plot_27a gnuplot_plot_28a gnuplot_plot_29a gnuplot_plot_30a gnuplot_plot_31a gnuplot_plot_32a gnuplot_plot_33a gnuplot_plot_34a gnuplot_plot_35a gnuplot_plot_36a gnuplot_plot_37a gnuplot_plot_38a gnuplot_plot_39a gnuplot_plot_40a gnuplot_plot_41a gnuplot_plot_42a gnuplot_plot_43a gnuplot_plot_44a gnuplot_plot_45a gnuplot_plot_46a gnuplot_plot_47a gnuplot_plot_48a gnuplot_plot_49a gnuplot_plot_50a gnuplot_plot_51a gnuplot_plot_52a gnuplot_plot_53a gnuplot_plot_54a gnuplot_plot_55a gnuplot_plot_56a gnuplot_plot_57a gnuplot_plot_58a gnuplot_plot_59a gnuplot_plot_60a gnuplot_plot_61a gnuplot_plot_62a gnuplot_plot_63a gnuplot_plot_64a gnuplot_plot_65a gnuplot_plot_66a gnuplot_plot_67a gnuplot_plot_68a gnuplot_plot_69a gnuplot_plot_70a gnuplot_plot_71a gnuplot_plot_72a gnuplot_plot_73a gnuplot_plot_74a gnuplot_plot_75a gnuplot_plot_76a gnuplot_plot_77a gnuplot_plot_78a gnuplot_plot_79a gnuplot_plot_80a gnuplot_plot_81a gnuplot_plot_82a gnuplot_plot_83a gnuplot_plot_84a gnuplot_plot_85a gnuplot_plot_86a gnuplot_plot_87a gnuplot_plot_88a gnuplot_plot_89a gnuplot_plot_90a gnuplot_plot_91a gnuplot_plot_92a gnuplot_plot_93a gnuplot_plot_94a gnuplot_plot_95a gnuplot_plot_96a gnuplot_plot_97a gnuplot_plot_98a gnuplot_plot_99a gnuplot_plot_100a gnuplot_plot_101a gnuplot_plot_102a gnuplot_plot_103a gnuplot_plot_104a gnuplot_plot_105a gnuplot_plot_106a gnuplot_plot_107a gnuplot_plot_108a gnuplot_plot_109a gnuplot_plot_110a gnuplot_plot_111a gnuplot_plot_112a gnuplot_plot_113a gnuplot_plot_114a gnuplot_plot_115a gnuplot_plot_116a gnuplot_plot_117a gnuplot_plot_118a gnuplot_plot_119a gnuplot_plot_120a gnuplot_plot_121a gnuplot_plot_122a gnuplot_plot_123a gnuplot_plot_124a gnuplot_plot_125a gnuplot_plot_126a gnuplot_plot_127a gnuplot_plot_128a gnuplot_plot_129a gnuplot_plot_130a gnuplot_plot_131a gnuplot_plot_132a gnuplot_plot_133a gnuplot_plot_134a gnuplot_plot_135a gnuplot_plot_136a gnuplot_plot_137a gnuplot_plot_138a gnuplot_plot_139a gnuplot_plot_140a gnuplot_plot_141a gnuplot_plot_142a gnuplot_plot_143a gnuplot_plot_144a gnuplot_plot_145a gnuplot_plot_146a gnuplot_plot_147a gnuplot_plot_148a gnuplot_plot_149a gnuplot_plot_150a gnuplot_plot_151a gnuplot_plot_152a gnuplot_plot_153a gnuplot_plot_154a gnuplot_plot_155a gnuplot_plot_156a gnuplot_plot_157a gnuplot_plot_158a gnuplot_plot_159a gnuplot_plot_160a gnuplot_plot_161a gnuplot_plot_162a gnuplot_plot_163a gnuplot_plot_164a gnuplot_plot_165a gnuplot_plot_166a gnuplot_plot_167a gnuplot_plot_168a gnuplot_plot_169a gnuplot_plot_170a gnuplot_plot_171a gnuplot_plot_172a gnuplot_plot_173a gnuplot_plot_174a gnuplot_plot_175a gnuplot_plot_176a gnuplot_plot_177a gnuplot_plot_178a gnuplot_plot_179a gnuplot_plot_180a gnuplot_plot_181a gnuplot_plot_182a gnuplot_plot_183a gnuplot_plot_184a gnuplot_plot_185a gnuplot_plot_186a gnuplot_plot_187a gnuplot_plot_188a gnuplot_plot_189a gnuplot_plot_190a gnuplot_plot_191a gnuplot_plot_192a gnuplot_plot_193a gnuplot_plot_194a gnuplot_plot_195a gnuplot_plot_196a gnuplot_plot_197a gnuplot_plot_198a gnuplot_plot_199a gnuplot_plot_200a gnuplot_plot_201a gnuplot_plot_202a gnuplot_plot_203a gnuplot_plot_204a gnuplot_plot_205a gnuplot_plot_206a gnuplot_plot_207a gnuplot_plot_208a gnuplot_plot_209a gnuplot_plot_210a gnuplot_plot_211a gnuplot_plot_212a gnuplot_plot_213a gnuplot_plot_214a gnuplot_plot_215a gnuplot_plot_216a gnuplot_plot_217a gnuplot_plot_218a gnuplot_plot_219a gnuplot_plot_220a gnuplot_plot_221a gnuplot_plot_222a gnuplot_plot_223a gnuplot_plot_224a gnuplot_plot_225a gnuplot_plot_226a gnuplot_plot_227a gnuplot_plot_228a gnuplot_plot_229a gnuplot_plot_230a gnuplot_plot_231a gnuplot_plot_232a gnuplot_plot_233a gnuplot_plot_234a gnuplot_plot_235a gnuplot_plot_236a gnuplot_plot_237a gnuplot_plot_238a gnuplot_plot_239a gnuplot_plot_240a gnuplot_plot_241a gnuplot_plot_242a gnuplot_plot_243a gnuplot_plot_244a gnuplot_plot_245a gnuplot_plot_246a gnuplot_plot_247a gnuplot_plot_248a gnuplot_plot_249a gnuplot_plot_250a gnuplot_plot_251a gnuplot_plot_252a gnuplot_plot_253a gnuplot_plot_254a gnuplot_plot_255a gnuplot_plot_256a gnuplot_plot_257a gnuplot_plot_258a gnuplot_plot_259a gnuplot_plot_260a gnuplot_plot_261a gnuplot_plot_262a gnuplot_plot_263a gnuplot_plot_264a gnuplot_plot_265a gnuplot_plot_266a gnuplot_plot_267a gnuplot_plot_268a gnuplot_plot_269a gnuplot_plot_270a gnuplot_plot_271a gnuplot_plot_272a gnuplot_plot_273a gnuplot_plot_274a gnuplot_plot_275a gnuplot_plot_276a gnuplot_plot_277a gnuplot_plot_278a gnuplot_plot_279a gnuplot_plot_280a gnuplot_plot_281a gnuplot_plot_282a gnuplot_plot_283a gnuplot_plot_284a gnuplot_plot_285a gnuplot_plot_286a gnuplot_plot_287a gnuplot_plot_288a gnuplot_plot_289a gnuplot_plot_290a gnuplot_plot_291a gnuplot_plot_292a gnuplot_plot_293a gnuplot_plot_294a gnuplot_plot_295a gnuplot_plot_296a gnuplot_plot_297a gnuplot_plot_298a gnuplot_plot_299a gnuplot_plot_300a gnuplot_plot_301a gnuplot_plot_302a gnuplot_plot_303a gnuplot_plot_304a gnuplot_plot_305a gnuplot_plot_306a gnuplot_plot_307a gnuplot_plot_308a gnuplot_plot_309a gnuplot_plot_310a gnuplot_plot_311a gnuplot_plot_312a gnuplot_plot_313a gnuplot_plot_314a gnuplot_plot_315a gnuplot_plot_316a gnuplot_plot_317a gnuplot_plot_318a gnuplot_plot_319a gnuplot_plot_320a gnuplot_plot_321a gnuplot_plot_322a gnuplot_plot_323a gnuplot_plot_324a gnuplot_plot_325a gnuplot_plot_326a gnuplot_plot_327a gnuplot_plot_328a gnuplot_plot_329a gnuplot_plot_330a gnuplot_plot_331a gnuplot_plot_332a gnuplot_plot_333a gnuplot_plot_334a gnuplot_plot_335a gnuplot_plot_336a gnuplot_plot_337a gnuplot_plot_338a gnuplot_plot_339a gnuplot_plot_340a gnuplot_plot_341a gnuplot_plot_342a gnuplot_plot_343a gnuplot_plot_344a gnuplot_plot_345a gnuplot_plot_346a gnuplot_plot_347a gnuplot_plot_348a gnuplot_plot_349a gnuplot_plot_350a gnuplot_plot_351a gnuplot_plot_352a gnuplot_plot_353a gnuplot_plot_354a gnuplot_plot_355a gnuplot_plot_356a gnuplot_plot_357a gnuplot_plot_358a gnuplot_plot_359a gnuplot_plot_360a gnuplot_plot_361a gnuplot_plot_362a gnuplot_plot_363a gnuplot_plot_364a gnuplot_plot_365a gnuplot_plot_366a gnuplot_plot_367a gnuplot_plot_368a gnuplot_plot_369a gnuplot_plot_370a gnuplot_plot_371a gnuplot_plot_372a gnuplot_plot_373a gnuplot_plot_374a gnuplot_plot_375a gnuplot_plot_376a gnuplot_plot_377a gnuplot_plot_378a gnuplot_plot_379a gnuplot_plot_380a gnuplot_plot_381a gnuplot_plot_382a gnuplot_plot_383a gnuplot_plot_384a gnuplot_plot_385a gnuplot_plot_386a gnuplot_plot_387a gnuplot_plot_388a gnuplot_plot_389a gnuplot_plot_390a gnuplot_plot_391a gnuplot_plot_392a gnuplot_plot_393a gnuplot_plot_394a gnuplot_plot_395a gnuplot_plot_396a gnuplot_plot_397a gnuplot_plot_398a gnuplot_plot_399a gnuplot_plot_400a gnuplot_plot_401a gnuplot_plot_402a gnuplot_plot_403a gnuplot_plot_404a gnuplot_plot_405a gnuplot_plot_406a gnuplot_plot_407a gnuplot_plot_408a gnuplot_plot_409a gnuplot_plot_410a gnuplot_plot_411a gnuplot_plot_412a gnuplot_plot_413a gnuplot_plot_414a gnuplot_plot_415a gnuplot_plot_416a gnuplot_plot_417a gnuplot_plot_418a gnuplot_plot_419a gnuplot_plot_420a gnuplot_plot_421a gnuplot_plot_422a gnuplot_plot_423a gnuplot_plot_424a gnuplot_plot_425a gnuplot_plot_426a gnuplot_plot_427a gnuplot_plot_428a gnuplot_plot_429a gnuplot_plot_430a gnuplot_plot_431a gnuplot_plot_432a gnuplot_plot_433a gnuplot_plot_434a gnuplot_plot_435a gnuplot_plot_436a gnuplot_plot_437a gnuplot_plot_438a gnuplot_plot_439a gnuplot_plot_440a gnuplot_plot_441a gnuplot_plot_442a gnuplot_plot_443a gnuplot_plot_444a gnuplot_plot_445a gnuplot_plot_446a gnuplot_plot_447a gnuplot_plot_448a gnuplot_plot_449a gnuplot_plot_450a gnuplot_plot_451a gnuplot_plot_452a gnuplot_plot_453a gnuplot_plot_454a gnuplot_plot_455a gnuplot_plot_456a gnuplot_plot_457a gnuplot_plot_458a gnuplot_plot_459a gnuplot_plot_460a gnuplot_plot_461a gnuplot_plot_462a gnuplot_plot_463a gnuplot_plot_464a gnuplot_plot_465a gnuplot_plot_466a gnuplot_plot_467a gnuplot_plot_468a gnuplot_plot_469a gnuplot_plot_470a gnuplot_plot_471a gnuplot_plot_472a gnuplot_plot_473a gnuplot_plot_474a gnuplot_plot_475a gnuplot_plot_476a gnuplot_plot_477a gnuplot_plot_478a gnuplot_plot_479a gnuplot_plot_480a gnuplot_plot_481a gnuplot_plot_482a gnuplot_plot_483a gnuplot_plot_484a gnuplot_plot_485a gnuplot_plot_486a gnuplot_plot_487a gnuplot_plot_488a gnuplot_plot_489a gnuplot_plot_490a gnuplot_plot_491a gnuplot_plot_492a gnuplot_plot_493a gnuplot_plot_494a gnuplot_plot_495a gnuplot_plot_496a gnuplot_plot_497a gnuplot_plot_498a gnuplot_plot_499a gnuplot_plot_500a gnuplot_plot_501a gnuplot_plot_502a gnuplot_plot_503a gnuplot_plot_504a gnuplot_plot_505a gnuplot_plot_506a gnuplot_plot_507a gnuplot_plot_508a gnuplot_plot_509a gnuplot_plot_510a gnuplot_plot_511a gnuplot_plot_512a gnuplot_plot_513a gnuplot_plot_514a gnuplot_plot_515a gnuplot_plot_516a gnuplot_plot_517a gnuplot_plot_518a gnuplot_plot_519a gnuplot_plot_520a gnuplot_plot_521a gnuplot_plot_522a gnuplot_plot_523a gnuplot_plot_524a gnuplot_plot_525a gnuplot_plot_526a gnuplot_plot_527a gnuplot_plot_528a gnuplot_plot_529a gnuplot_plot_530a gnuplot_plot_531a gnuplot_plot_532a gnuplot_plot_533a gnuplot_plot_534a gnuplot_plot_535a gnuplot_plot_536a gnuplot_plot_537a gnuplot_plot_538a gnuplot_plot_539a gnuplot_plot_540a gnuplot_plot_541a gnuplot_plot_542a gnuplot_plot_543a gnuplot_plot_544a gnuplot_plot_545a gnuplot_plot_546a gnuplot_plot_547a gnuplot_plot_548a gnuplot_plot_549a gnuplot_plot_550a gnuplot_plot_551a gnuplot_plot_552a gnuplot_plot_553a gnuplot_plot_554a gnuplot_plot_555a gnuplot_plot_556a gnuplot_plot_557a gnuplot_plot_558a gnuplot_plot_559a gnuplot_plot_560a gnuplot_plot_561a gnuplot_plot_562a gnuplot_plot_563a gnuplot_plot_564a gnuplot_plot_565a gnuplot_plot_566a gnuplot_plot_567a gnuplot_plot_568a gnuplot_plot_569a gnuplot_plot_570a gnuplot_plot_571a gnuplot_plot_572a gnuplot_plot_573a gnuplot_plot_574a gnuplot_plot_575a gnuplot_plot_576a gnuplot_plot_577a gnuplot_plot_578a gnuplot_plot_579a gnuplot_plot_580a gnuplot_plot_581a gnuplot_plot_582a gnuplot_plot_583a gnuplot_plot_584a gnuplot_plot_585a gnuplot_plot_586a gnuplot_plot_587a gnuplot_plot_588a gnuplot_plot_589a gnuplot_plot_590a gnuplot_plot_591a gnuplot_plot_592a gnuplot_plot_593a gnuplot_plot_594a gnuplot_plot_595a gnuplot_plot_596a gnuplot_plot_597a gnuplot_plot_598a gnuplot_plot_599a gnuplot_plot_600a gnuplot_plot_601a gnuplot_plot_602a gnuplot_plot_603a gnuplot_plot_604a gnuplot_plot_605a gnuplot_plot_606a gnuplot_plot_607a gnuplot_plot_608a gnuplot_plot_609a gnuplot_plot_610a gnuplot_plot_611a gnuplot_plot_612a gnuplot_plot_613a gnuplot_plot_614a gnuplot_plot_615a gnuplot_plot_616a gnuplot_plot_617a gnuplot_plot_618a gnuplot_plot_619a gnuplot_plot_620a gnuplot_plot_621a gnuplot_plot_622a gnuplot_plot_623a gnuplot_plot_624a gnuplot_plot_625a

注意:

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

  • $n>0$の時、グラフの描画をしなく、与えられる線分の再分割を行います。さらに、各新しい線分に対して、関数自身を呼びます。
  • $n=0$の時、線分の処理をしなく、線分を描画します。

レポート課題

フラクタルを自分で設計して、作成してください。

  • 既知のフラクタルの例でもよいです。
  • Minkowski Sausageのフラクタルを再帰的な計算で作成しても良いです。
  • Kohn曲線とツリーは不可です。しかし、Kohn曲線またはツリーを大幅に改造したものはO.K.です。(再分割の割合や、回転の角度など)

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

In [ ]: