６章 再帰を用いた作図
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
再帰とは「手続きや関数の中で、その手続きや関数自身を呼び出すこと」で、計算の規則性がわかればプログラミングを効率化することができる。
代表的な例 ： 階乗の計算
ｎの階乗は次のようにして計算される
ｎ! は、ｎ と (n-1)! との積、 (n-1)! は (n-1)と(n-2)! との積 … … となっていることに着目して以下のプログラミングを行う。ここで、0! = 1 である。
→解説へ
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
Editコンポーネントを２個使用して、下図のように実行する。実行ボタンを押した後、最初のEditコンポーネントから数値を入力し、ボタンをクリックし、もう１つのEditコンポーネント上に計算結果を得る。
プログラミング）
（先頭部分省略）
var
Form1: TForm1;
function fact( n:integer ) : integer; // （関数の宣言）
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var
n, kaijyou : integer;
begin
n := StrToInt(Edit1.Text); //（数値の読みこみ）
kaijyou := fact(n); //（関数の呼び出し）
Edit2.Text := IntToStr(kaijyou); // （計算結果の表示）
end;
function fact( n:integer ) : integer; //（階乗を計算する関数）
begin
if n = 0 then fact := 1
else fact := n * fact(n-1);
end;
end.
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
手続き(procedure)と同様に、特定の処理を行なうプログラムに名前を付け、その名前を使って呼び出すことで計算が行なわれるが、｢関数名を介して計算結果を返すことができる｣点が大きな違いである。関数を定義する方法は、
function 関数名（ 引数：型 ） ： 関数の型 ；
である。上記の例では、関数は次のようになっている。関数名はfactで、呼び出し側において整数型の変数ｎに値が入れられ、関数factにその値が渡される。計算結果は整数が返される。
ここで、呼び出し側も見ておこう。整数型の変数ｎの値をEditコンポーネントから入力し、それを変数ｎ（このように、呼び出される側の関数に値を渡すための変数を引数（ひきすう）と呼んでいる）入れて、関数factを呼び出している。関数名が通常の変数名と同じように扱われて、変数kaijyouへの代入が行なわれていることに注意しよう。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
上記の例は、｢関数(function)｣の再帰呼び出しを行なって、値を返す場合を扱ったが、今度は｢手続き(procedure)｣の再帰呼び出しによって、図を描くことにする。
例題は以下の通りである。手続きの呼び出しごとに、大きさがもとの大きさの半分の正方形を描いていく。（このような作図は再帰を用いなくても描けるが、直感的な理解のために用いた）図中で(3)の位置にある正方形は、辺の長さが(2)の正方形の半分、(2)は(1)の半分となっている。
プログラム）
（先頭部分省略）
var
Form1: TForm1;
procedure rectangle_draw( len:real); // （手続きの宣言）
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var
len : real;
begin
len := 200; （辺の長さの初期値）
rectangle_draw(len); （手続きの呼び出し）
end;
procedure rectangle_draw(len:real);
var x1,y1,x2,y2, w : integer;
begin
x1 := 50; // （正方形の左上の頂点の位置）
y1 := 50;
w := round(len); // （小数部切り捨てによる数値の整数化）
x2 := x1 + w; // （正方形の右下の頂点の位置）
y2 := y1 + w;
if ( len > 3 ) then begin // （長さが３を超えていれば作図）
Form1.Canvas.Rectangle(x1,y1,x2,y2);
len := len / 2; // （辺の長さを半分にする）
rectangle_draw(len); // （手続きが自分自身を再帰呼び出し）
end;
end;
end.
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
再帰的な処理の流れ
上記のプログラムにおいて、手続きが自分自身を呼び出すときの処理の流れを、下図の番号順に見ていこう。まず、(1)において、引数に値200が入れられて関数が最初に呼び出される。この値を受け取った手続きrectangle_drawは、(3)において正方形の頂点位置を計算する。作図を行なうかどうかの判定の条件は、辺の長さが３よりも大きいことであるから、この場合には作図が実行される。1個の正方形を描いた後、辺の長さを半分にする。今度は値100を手続きに渡すことになるが、ここで｢再帰的呼び出し｣が始まる。
再帰的な呼び出しの第１回目を図示すると次のようになる。
以下同様にして、( len > 3 ) の条件が成り立っている間、この処理を繰り返すことになる。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
手続きの再帰呼び出しによって、樹木曲線を描く。樹木曲線の作図は次の規則に従って行われる。
@ ０次の樹木曲線は長さLの直線である。
A １次の樹木曲線は長さL/2の枝を90oの角をなして２本だす。
B ２次の樹木曲線は長さL/4の枝を90oの角をなして、Aの各枝から２本出す。
同様の操作を３次以降に関しても繰り返す。
出力例： 12次の樹木曲線
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
プログラム）
（先頭部分省略）
var
Form1: TForm1;
pai : real = 3.1415 ;
scale, branch1, branch2 : real;
xc, yc : integer;
procedure tree( n, xs, ys : integer; len, angle: real);
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var xs, ys, n : integer;
len, angle : real;
begin
xs := 0; ys := 0; //（計算上の原点位置）
xc := 200; yc := 400; //（画面上の原点位置）
len := 80; //（線分長さの初期値）
angle := 90; //（枝の傾きの初期値）
scale := 1.4; //（辺の長さの縮小倍率）
n := StrToInt(Edit1.Text);
branch1 := StrToInt(Edit2.Text);
branch2 := StrToInt(Edit3.Text);
tree( n, xs, ys, len, angle );
end;
procedure tree( n, xs, ys : integer; len, angle: real);
var th : real;
x2, y2 : integer;
begin
if ( n >= 0 ) then
begin
th := pai * angle / 180;
x2 := xs + round( len * cos(th) );
y2 := ys + round( len * sin(th) ); // →sin,cosの使い方は８章で・・・
Form1.Canvas.MoveTo( xc + xs, yc - ys );
Form1.Canvas.LineTo( xc + x2, yc - y2 );
// right branching
tree( n-1, x2, y2, len/scale, angle - branch1 );
// left branching
tree( n-1, x2, y2, len/scale, angle + branch2 );
end;
end;
end.
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
補足１） 実行時の入力
上記のプログラムを実行には次の３つの値を必要とする。
(1) 曲線の次数（＝再帰呼び出しを何回繰り返すか）
(2) 左側の枝分かれの角度
(3) 右側の枝分かれの角度である。
プログラム内で傾き角を表す変数は
branch1 : 右傾き角
branch2 : 左傾き角
である。上記のプログラムでは、これらの傾き角は、手続きの呼び出し時に次のように使われている。
// right branching
tree( n-1, x2, y2, len/scale, angle - branch1 );
// left branching
tree( n-1, x2, y2, len/scale, angle + branch2 );
右の枝分かれをするときには、基準となる角度(angle)からbranch1の値の分を引き、左の枝分かれをするときにはbranch2の値の分を加える。
樹木曲線の次数、右傾き角、左傾き角の入力はStrToInt命令(StringをIntegerに変換する)によって行う。
n := StrToInt(Edit1.Text);
branch1 := StrToInt(Edit2.Text);
branch2 := StrToInt(Edit3.Text);
これらの値をForm上で入力しない場合には、単にプログラム中に
n := 8;
branch1 := 45;
branch2 := 45;
などと書いておけばよい。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
補足２： 図形の原点と画面内の作図開始位置
グラフィック画面上では、垂直軸の正（プラス）の向きが通常の場合とは逆である。画面の左上隅が原点に相当し、この位置から右方向が水平軸の正方向、下方向が垂直軸の正方向となっている。
 |
このため、作図を行うときにはもとの図形が画面の中央付近で、本来の向きに描かれるように座標値の変換を行う必要がある。
このことを考慮するために、上記のプログラムでは、まず
xs := 0; ys := 0;
xc := 200; yc := 400;
としてある。xs,ysが図形の原点で、xc,ycが作図開始位置である。言いかえると、画面上の(200,400)のピクセル位置が樹木曲線の｢根元｣になる。
実際に線を描くときには、次のように変換を行っている。
Form1.Canvas.MoveTo( xc + xs, yc - ys ); （始点）
Form1.Canvas.LineTo( xc + x2, yc - y2 ); （終点）
水平方向についてはｘｃだけ増加させることによって水平方向のずれを補正し、垂直方向についてはｙｃから引くことによって図形の上下反転を直している。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
計算例）
xc = 200, yc = 400 を用いて上記の座標変換を行ってみる。図の左がもとの座標系での座標値、右がディスプレイ内での座標値である。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
出力例２： ８次の樹木曲線：枝の間の角度が30度の場合（左）と60度の場合（右）
左右の傾きを各々１５度ずつ、３０度ずつとして樹木曲線を描くと次のようになる。
出力例３： ８次の樹木曲線：枝の間の角度が60度（右に45度、左に15度の傾き）
左右の傾き角度を非対称にすると、下図のように成長が右側に偏ったような樹木曲線が得られる。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
正方形を枝にした樹木曲線を描いてみる。
樹木曲線の作図は次の規則に従って行われる。
@ 最初の正方形は番号順に書く
A 右の木に移ったときの始点の位置は次のように計算する
B 左の木に移ったときの始点の位置は次のように計算する
作図例） ７次の樹木曲線
プログラム）
（先頭部分省略）
var
Form1: TForm1;
pai : real = 3.1415;
rt2 : real = 1.4142;
scale , branch : real;
xc, yc : integer;
procedure tree( n, xs, ys: integer; len, angle: real );
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var xs, ys, n : integer;
len, angle : real;
begin
xs := 0; ys := 0;
xc := 300; yc := 300;
len := 60;
angle := 90;
n := StrToInt(Edit1.Text);
tree( n, xs, ys, len, angle );
end;
procedure tree( n, xs, ys: integer; len, angle: real );
var
th : real;
i, x2, y2, x1, y1 : integer;
begin
if ( n >= 0 ) then
begin
x1 := xs;
y1 := ys;
for i := 1 to 4 do
begin
angle := angle + 90;
th := pai * angle / 180;
x2 := x1 + round( len * cos(th) );
y2 := y1 + round( len * sin(th) );
Form1.Canvas.MoveTo( xc + x1, yc - y1 );
Form1.Canvas.LineTo( xc + x2, yc - y2 );
x1 := x2;
y1 := y2;
end;
// right branching
th := pai * ( angle - 45 ) / 180;
tree( n-1, xs + round( len * cos(th) / rt2 ),
ys + round( len * sin(th) / rt2 ),
len / rt2, angle - 45 ) ;
// left branching
th := pai * ( angle + 45 ) / 180;
tree( n-1, xs + round( rt2 * len * cos(th) ),
ys + round( rt2 * len * sin(th) ),
len / rt2, angle + 45 ) ;
end;
end;
end.