はじめに
「フラクタル図形」とは、その図形を拡大して行くと、再び最初の図形と同じものが現れる、特殊な図形です。自然界に多く見られ、海岸線や雲の形がフラクタルだと言われています。プログラミングの技術から見ると、フラクタルを描くためには「再帰プログラム」という、最初はちょっと理解し難い特殊なテクニックを使います。プログラミングの学習では、この再帰テクニックを習得するために、フラクタル画像の描画が良く使われます。
再帰プログラムは特殊な場合しか有効ではありませんが、スマートなので、テクニックを誇示したい人は使いたがります。
対象読者
「再帰プログラム」とは何か、どのようにコードを書けばよいかを学びたい人。情報処理技術者試験に出ることもあります。コードはJavaで書いてありますが、考え方は他の言語にも通用しますので、参考にしてください。
必要な環境
J2SE 5.0を使っていますが、それ以前のバージョンでも問題ありません。
フラクタル図形とは
フラクタル（Fractal）図形とは、マンデルブロー（Benoit Mandelbrot）が命名した言葉で、簡単に言うと、自己相似性を持ち、図形の一部を拡大すると、また同じような図形が現れるものを言います。マンデルブローの図形は、たしかにフラクタルの条件を備えていますが、再帰プログラムでは作りません。再帰プログラムで作るフラクタル図形の代表的なものにコッホ（Helge von Koch）曲線や樹木曲線、ドラゴン（竜）曲線などがあります。
再帰プログラムとは
再帰プログラムは、複雑な事柄を簡単に表現できる場合があり、関数呼び出しの場合の外部変数と内部変数との関係が良く理解できるので、教育的な効果があります。
再帰プログラムとは、呼び出された関数（メソッド）の中で、再び「自分自身」の関数を呼び出すものです。したがって、初心者には頭が混乱して理解し難い欠点があります。グローバルな変数（オブジェクト）だけしか使えない初期のプログラム言語では、再帰プログラムを組むことができませんでした。
再帰プログラムの関数は、自分自身を無限に呼び出すわけではありません。ある条件になると別の処理を実行して呼び出し元に戻ります。
再帰プログラムの特徴は、
- 関数の中に、自分自身を呼び出す命令が含まれている。
- 一定の条件（呼び出し回数、扱う数値の大きさなど）では自分自身を呼び出さないで別の命令を実行する「ストッパー」が用意されている。
- 関数を呼び出す毎に、呼び出し回数や数値が変更される。
ということです。
再帰プログラムの例
再帰プログラムの最も簡単な例として、nの階乗を求めるプログラムがあります。これは、n!=n x (n-1)!の関係を使います。n-1の階乗が分かれば、nの階乗が計算できますので、階乗を求める関数の中で、階乗を求める関数を再び呼び出します。
しかし、これはあまりにも簡単で、実行後に感動を覚えることもありません。したがって、ここでは、再帰プログラムの例としてよく知られるコッホ曲線、樹木曲線、ドラゴン（竜）曲線などのフラクタル図形の描画方法を紹介します。
いずれも、Javaアプレットとして作成され、サイズは500ｘ500を想定しています。
コッホ曲線
図1の一番上に示す直線に対してコッホ曲線描画メソッドを呼び出すと、図の中央に示すような折れ線に置き換えられます。図の場合、コッホ曲線描画メソッドは一回だけ実行して元に戻りますので、まだ再帰的な動作はしていません。一番下の図は、コッホ曲線描画メソッドが自分自身をもう一回呼び出して作られたもので、再帰回数が１回になります。この操作を一定回数だけ繰り返すとコッホ曲線が得られます。
コッホ曲線描画プログラムの説明
- メインプログラムを、
paintメソッドとして作成します。ここでは、コッホ曲線を描く基準となる逆正三角形を形成する３点（P、Q、R）を指定し、別途作成するdrawKochメソッドをそれぞれ一回ずつ呼び出します。 - このプログラムで最も重要な
drawKochメソッドを作成します。このメソッドは、以下に説明する処理から成っています。
図2は、外部から与えられた元の直線の座標（点Aと点B）から、点C、点D、点Eを求めてコッホ曲線を描く方法の原理を示しています。点Cおよび点Dは、点Aと点Bの間を3等分することで容易に求められます。
点Eについては、点A－点Cと、点A－点Eの作る角度が30°（Math.PI/6）であることに注目し、点A－点Bの傾斜角Math.atan((double)yy/xx)にMath.PI/6を加算して、点A－点Eの角度を求めます。点A－点Eの長さdistanceは、点A－点Bの長さの1/√3です。ここで、yyは整数（int）ですので、割り算を精密に行うためにdoubleにキャストしています。
実際にはE点の座標の計算はやや面倒で、図形を左下から右上に向かって描く場合とその逆の場合、左上から右下に向かって描く場合とその逆の場合などで、若干の工夫が必要になります。また、パソコン画面上では、下に行くほどyの値が大になるので、極性に注意する必要があります。
再帰を繰り返している間（n>0）は、点A－点C、点C－点E、点E－点D、点D－点B間を描画すために、更にdrawKochメソッドを呼び出し、最後（n=0）には、点A－点C、点C－点E、点E－点D、点D－点Bを、drawLine関数により直線で描画します。
import java.applet.Applet; import java.awt.*; public class Koch extends Applet{ public void init(){ setBackground(Color.yellow); //背景を黄色で描きます } public void paint(Graphics g){ //出発点となる３点を指定します Point P=new Point(100,160); Point Q=new Point(400,160); Point R=new Point(250,420); //線色を青色に設定した後、上記３点の間にコッホ曲線を描きます g.setColor(Color.blue); drawKoch(g,P,Q,3); drawKoch(g,Q,R,3); drawKoch(g,R,P,3); } //コッホ曲線を描くメソッド public void drawKoch(Graphics g,Point a,Point b,int n){ //メソッド内部で使用する３点を生成します Point c=new Point(); Point d=new Point(); Point e=new Point(); int xx,yy; double angle1,angle2,distance; c.x=(2*a.x+b.x)/3; c.y=(2*a.y+b.y)/3; d.x=(a.x+2*b.x)/3; d.y=(a.y+2*b.y)/3; xx=b.x-a.x; yy=-(b.y-a.y); distance=Math.sqrt(xx*xx+yy*yy)/Math.sqrt(3); if(xx>=0){ //元になる直線が右上がりの場合 angle1=Math.atan((double)yy/xx)+Math.PI/6; e.x=a.x+(int)(distance*Math.cos(angle1)); e.y=a.y-(int)(distance*Math.sin(angle1)); } else{ //元になる直線が右下がりの場合 angle2=Math.atan((double)yy/xx)-Math.PI/6; e.x=b.x+(int)(distance*Math.cos(angle2)); e.y=b.y-(int)(distance*Math.sin(angle2)); } //最後なので、実際に線を引きます if(n<=0){ g.drawLine(a.x,a.y,c.x,c.y); //点Aから点Cへ g.drawLine(c.x,c.y,e.x,e.y); //点Cから点Eへ g.drawLine(e.x,e.y,d.x,d.y); //点Eから点Dへ g.drawLine(d.x,d.y,b.x,b.y); //点Dから点Bへ } //最後ではないので、更にメソッドを呼び出します（再帰処理） else{ drawKoch(g,a,c,n-1); //点Aから点Cへ drawKoch(g,c,e,n-1); //点Cから点Eへ drawKoch(g,e,d,n-1); //点Eから点Dへ drawKoch(g,d,b,n-1); //点Dから点Bへ } } }
コッホ曲線描画プログラムの実行結果
結果を図3に示します。このような図形を「コッホ島」と呼ぶことがあります。Javaアプレットはこちらをご覧ください。
樹木曲線
樹木曲線を描画するには、いくつか方法がありますが、ここでは例として、図4に示すように、図の左に示した元の直線を右側の図のように変換することにします。右の図は下から一定の割合の部分を幹と想定し、そこから左右に枝を伸ばした様子を示しています。縦に伸びる直線の残りの部分（すなわち、元の直線から下の幹の部分を除いたもの）の長さに対して、枝の長さを一定の割合にします。幹を除いた縦に伸びる中心の部分と左右の枝の部分に、再びこれと同じ変更を一定回数だけ繰り返すと樹木曲線ができます。一例として枝の出る角度を「30°」にしています。
樹木曲線描画プログラムの説明
- メインプログラムを、
paintメソッドとして作成します。ここでは、樹木曲線を描くためのパソコン画面上の点を３対だけ指定し（PとQ、RとS、TとU）、別途作成するdrawTreeメソッドをそれぞれ、一回ずつ呼び出します。例では、画面上の点P(200,400)、点Q(200,100)などを用い、再帰の回数はそれぞれ、3、4、5回にしてあります。 - このプログラムで最も重要な
drawTreeメソッドを作成します。STEM_RATIOとBRANCHI_RATIOは、定数として与えます。
図5は、外部から与えられた元の直線の座標（点Aと点B）から、点C、点D、点Eを求める方法を示します。図に示すように、点CはSTEM_RATIOから簡単に求まります。
点Dについては、点C－点Bと、点C－点Dの作る角度が30°（Math.PI/6）であることに注目し、点A－点Bの傾斜角Math.atan(yy/xx)にMath.PI/6を加算してangle1を求めます。同様に、点Eの角度angle2を求めます。angle1とangle2が分かれば、点Dと点Eの座標は、三角関数により簡単に求まります。
念のために、各変数・定数の説明をします。
| 変数・定数 | 説明 |
STEM_RATIO | 与えられた直線のどれだけの部分を幹と見なすかの割合 |
center_length | 与えられた直線から幹の部分を引いた残りの長さ |
BRANCH_RATIO | center_lengthに対して、横に出る枝の長さの割合 |
branch_length | 横に出る枝の長さ |
angle1 | 左側の枝の角度 |
angle2 | 右側の枝の角度 |
sign | 与えられた直線の向きで座標の増減の向きが変わるので、それを制御するための、1または-1の値 |
import java.applet.Applet; import java.awt.*; public class Tree extends Applet{ public void init(){ setBackground(Color.yellow); } public void paint(Graphics g){ //３対の点を指定します Point P=new Point(100,400); Point Q=new Point(100,100); Point R=new Point(250,400); Point S=new Point(250,100); Point T=new Point(400,400); Point U=new Point(400,100); //それぞれの対をなす２点間に樹木曲線を描きます g.setColor(Color.blue); drawTree(g,P,Q,3); drawTree(g,R,S,4); drawTree(g,T,U,5); } //樹木曲線を描くメソッド public void drawTree(Graphics g,Point a,Point b,int n){ double STEM_RATIO=0.25,BRANCH_RATIO=0.6; Point c=new Point(); Point d=new Point(); Point e=new Point(); int sign; int xx,yy; double angle1,angle2,center_length,branch_length; xx=b.x-a.x; yy=-(b.y-a.y); angle1=Math.atan((double)yy/xx)+Math.PI/6; angle2=Math.atan((double)yy/xx)-Math.PI/6; center_length=Math.sqrt(xx*xx+yy*yy)*(1-STEM_RATIO); branch_length=BRANCH_RATIO*center_length; //元の直線が右下がりなら符号をマイナスにします sign=(xx>=0)? 1:-1; c.x=(int)(a.x+STEM_RATIO*xx); c.y=(int)(a.y-STEM_RATIO*yy); d.x=c.x+sign*(int)(branch_length*Math.cos(angle1)); d.y=c.y-sign*(int)(branch_length*Math.sin(angle1)); e.x=c.x+sign*(int)(branch_length*Math.cos(angle2)); e.y=c.y-sign*(int)(branch_length*Math.sin(angle2)); //幹の部分は再帰を行わないので、点Aから点Cへ実際に線を引きます g.drawLine(a.x,a.y,c.x,c.y); //最後なので、実際に線を引きます if(n<=0){ g.drawLine(c.x,c.y,b.x,b.y); //中央部（点Cから点Bへ） g.drawLine(c.x,c.y,d.x,d.y); //左の枝（点Cから点Dへ） g.drawLine(c.x,c.y,e.x,e.y); //右の枝（点Cから点Eへ） } //最後ではないので、更にメソッドを呼び出します（再帰処理） else{ drawTree(g,c,b,n-1); //中央部（点Cから点Bへ） drawTree(g,c,d,n-1); //左の枝（点Cから点Dへ） drawTree(g,c,e,n-1); //右の枝（点Cから点Eへ） } } }
樹木曲線描画プログラムの実行結果
結果を図6に示します。再帰の繰り返し回数（左から、3回、4回、5回）によって、次第に樹らしくなって行く様子がわかります。この他にも、条件を変えて樹を描くと、面白い結果が得られると思います。Javaアプレットはこちらをご覧ください。
ドラゴン（竜）曲線
できた結果が、中国風のドラゴン（竜）に似ているところから、この名称があります。図7の左最上部に示す一本の直線を、その下（再帰回数0回と書かれている）にあるように二本の直線に置き換え、これを再帰的に繰り返しますと、次第にドラゴンに変わって行きます。
ドラゴン曲線描画プログラムの説明
- メインプログラムを、
paintメソッドとして作成します。ここでは、ドラゴン曲線を描くためのパソコン画面上の座標を二点だけ指定し（PとQ）、二点間にドラゴン曲線を描くためにdrawDragonメソッドを一回呼び出すだけです。 - このプログラムで最も重要な
drawDragonメソッドを作成します。このメソッドは、与えられた元の直線の位置を示す点Aと点Bの座標から、折り曲げに必要な点Cの座標を求め、再び自分自身を呼び出します。点Cの座標は、図8の右に示す方法で得られます。図で、塗りつぶした三つの三角形は同じ形と大きさなので、点Cの座標が容易に求まります。描画は、点Aから点Cに向かう直線と、点Bから点Cに向かう直線（点Cから点Bに向かって逆に引いてはいけない）の二本の直線を描きます。
import java.applet.Applet; import java.awt.*; public class Dragon extends Applet{ public void init(){ setBackground(Color.yellow); } public void paint(Graphics g){ //出発点となる一対の点を指定します Point P=new Point(170,140); Point Q=new Point(400,350); //対となる二点の間にドラゴン曲線を描きます g.setColor(Color.blue); drawDragon(g,P,Q,10); } //ドラゴン曲線を描くメソッド public void drawDragon(Graphics g,Point a,Point b,int n){ Point c=new Point(); int xx,yy; xx=b.x-a.x; yy=-(b.y-a.y); c.x=a.x+(xx+yy)/2; c.y=b.y+(xx+yy)/2; //最後なので、実際に線を引きます if(n<=0){ g.drawLine(a.x,a.y,c.x,c.y); //点Aから点Cへ g.drawLine(b.x,b.y,c.x,c.y); //点Bから点Cへ } //最後ではないので、さらにメソッドを呼び出します（再帰処理） else{ drawDragon(g,a,c,n-1); //点Aから点Cへ drawDragon(g,b,c,n-1); //点Bから点Cへ } } }
ドラゴン曲線描画プログラムの実行結果
実際に得られた結果を図9に示します。ドラゴン（竜）に見えるでしょうか。再帰は10回繰り返してあります。Javaアプレットはこちらをご覧ください。
まとめ
再帰プログラムは決して難しくないことが分かりましたでしょうか。drawKochなどの再帰メソッドを作成するには、図形描画のための若干の幾何学的発想が必要になりますが、これが知恵の出し所で、面白いところです。皆さんも、新しいフラクタル図形を描いてみてください。
他の文献や資料では、フラクタル図形の描画に「タートル・グラフィックス」という特殊な描画技法を使うものが多いのですが、この記事ではそれを使わなくても直接描けることを示したつもりです。タートル・グラフィックスは、描画を亀の移動に見立て、画面上の絶対座標や角度に依らず、それまでの移動方向からの変化角と相対的な移動距離を与えて直線を描く方法です。これを使用するためには、専用のクラス・ライブラリを入手するか作成する必要があります。
参考資料
この記事は、筆者のホームページ「Visual C++の易しい使い方（14）－再帰プログラムの例題としてのフラクタル図形の描画－（ただし、現在はVisual C++ 2005 Express Edition版に改定）」をJava言語に書き直し、分かりやすく加筆したものです。
ちなみに、タートル・グラフィックスを使用しているものには、以下の資料があります。
- 『Javaによるアルゴリズム事典』 奥村晴彦他 著、技術評論社、2003年5月
- 『Javaによるはじめてのアルゴリズム入門』 河西朝雄 著、技術評論社、2001年6月
- 『Javaグラフィックス完全制覇』 芹沢浩 著、技術評論社、2001年12月
