この実験について
木は、幹の上に小さな木が二つあるものです。この一文だけで完全なプログラムになります。枝を描き、その後自分自身を二度呼び出す関数です。再帰は短い規則から豊かな絵を生み出します。木、シェルピンスキーの三角形、コッホ雪片が呼び出しごとに形作られていく様子を見て、呼び出しスタックが伸び縮みするのを追い、深さが増すにつれて呼び出し回数がどれほど急増するか数えてみましょう。
学習目標
- 再帰関数の基本ケースと再帰ケースを見分ける
- 再帰呼び出しが実行され、戻る順序を追跡する
- コールスタックに何が格納されているか、またその深さが重要な理由を説明してください
- 二分木の場合の 2^(n+1) − 1 のように、指定した深さに対する呼び出し回数を計算してください
- 自己相似性を説明し、簡単なフラクタル次元を計算してください
使い方
- 1深さ 3 の木を選び、呼び出しをゆっくり観察してください。左と右のどちらの枝が先に描かれますか？ それはなぜですか？
- 2スタックが最も深くなったところで一時停止してください。スタック上の各フレームは何を表していますか？ 深さと比べてフレームはいくつありますか？
- 3木の深さと呼び出し回数の表を完成させてください。規則を見つけ、深さ 10 で確かめてください。
- 4枝の角度と長さの比率を変えてください。どの設定で枝が重なりますか？
- 5シェルピンスキーの三角形に切り替えてください。コードのどこに基本ケースがありますか？ 深さ 5 では三角形はいくつ描かれますか？
- 6深さ 5 のコッホ雪片を作成してください。表示値を使って、周長が増え続けても面積が有限にとどまる理由を説明してください。
モデル
前提条件
- 呼び出しは通常のプログラミング言語とまったく同じように、プログラム上の順序で、深さ優先に一つずつ実行されます。
- 擬似コードでは位置と向きをパラメーターとして渡すため、呼び出しから戻った後にタートルの状態を復元する必要はありません。
- 木のフラクタル次元 log 2 / log(1/r) が枝先について表すのは、枝が重なり合わない場合だけです。
- 手順を一つずつ再生しても高速に動作するよう、最大深度を制限しています。木は12、三角形は7、雪片は6です。
授業で試してみましょう
- Q1木の関数にベースケースがなかったら、どうなるでしょうか？
- Q2深度4でシェルピンスキー関数は何回呼び出されますか？和を使って答えを説明してください。
- Q3何千回も呼び出しが行われるのに、呼び出しスタックの深さが再帰の深さに1を加えた値を超えないのはなぜですか？
- Q4n!を計算する再帰関数を書き、そのベースケースを特定してください。
- Q5測る定規が短いほど、イギリスの海岸線は長く見えます。コッホ雪片はこれをどのように説明するのでしょうか？
よくある質問
再帰はループより遅いのでしょうか？
呼び出しごとにスタックフレーム用の時間とメモリが少し必要になるため、ループのほうがやや速いことがよくあります。しかし、木構造や入れ子になったフォルダー、構文解析などの分岐構造では、再帰のほうがはるかに簡単に記述できます。また、どのような再帰も、自分で明示的なスタックを使う形に書き換えられます。
スタックオーバーフローとは何ですか？
終了していない呼び出しはそれぞれ、コールスタック上にフレームを保持します。再帰が深くなりすぎると、たとえば基底ケースに到達しない場合、スタックのメモリが尽き、プログラムはスタックオーバーフローエラーでクラッシュします。
自然界では、フラクタルはどこに見られますか？
シダ、ロマネスコ、河川網、稲妻、血管、肺の枝分かれした気道は、いずれも複数のスケールにわたっておおよそ自己相似です。そのため、コンピューターグラフィックスでは、それらを生成するために再帰的な規則が使われます。