以前、「分岐しない再帰関数」について解説しましたが、ここでは「分岐する再帰関数」について解説したいと思います。ただ、分岐する再帰関数はサンプルプログラムが巨大になりますので、自作ライブラリ MyCanvas内のソースコードをベースにして、ざっくり説明する形にしたいと思います。
分岐する再帰関数については、以下の 3つに細分化してそれぞれ説明していきます。
再帰関数は理解するのがなかなか難しく、またオブジェクト指向とは無関係なので、今すぐに完全理解する必要はないです。ただ、実際にプログラムを作る際、「稀に」再帰関数を使用するとすごくシンプルにソースコードを記述できるときがあるかもしれません。そういう意味で、いつかは理解しておきたい知識になります。
ずっと以前に紹介した D303.javaと同じソースコードですが、改めて J601.javaとして製作します。
J601/MyCanvas.java(ライブラリをそのまま利用します)
J601/J601.java
/**
* MyCanvasライブラリをテストします。
*/
public class J601 {
/**
* メインメソッド。
* @param args 引数
*/
public static void main(String[] args) {
MyCanvas.c.drawPoint(5, 2, 'a');
MyCanvas.c.drawLine(1, 1, 10, 10, 'b');
MyCanvas.c.drawLine(-10, 15, 25, 0, 'c');
MyCanvas.c.fill(15, 15, '+');
MyCanvas.c.drawRect(10, 10, 15, 13, 'd');
MyCanvas.c.drawRectFill(1, 15, 8, 18, 'e');
// 画面に表示する
MyCanvas.c.print();
}
}
実行結果は以下の通り。
.................... .b.................. ..b..a............cc ...b...........ccc++ ....b........ccc++++ .....b.....cc+++++++ ......b..cc+++++++++ ......ccc+++++++++++ ....cc++b+++++++++++ ..cc+++++b++++++++++ cc++++++++dddddd++++ c+++++++++d++++d++++ ++++++++++d++++d++++ ++++++++++dddddd++++ ++++++++++++++++++++ +eeeeeeee+++++++++++ +eeeeeeee+++++++++++ +eeeeeeee+++++++++++ +eeeeeeee+++++++++++ ++++++++++++++++++++
MyCanvasライブラリにはいろいろな機能があります。ソースコードを修正して、いろいろ実験してみてください。
線を描画するメソッド drawLineを見ていきます。MyCanvas.javaの 178行目以降を以下に抜粋します。
/**
* 線を描画します。
* @param x1 起点 X座標
* @param y1 起点 Y座標
* @param x2 終点 X座標
* @param y2 終点 Y座標
* @param c 文字
*/
public void drawLine(int x1, int y1, int x2, int y2, char c) {
this.drawLine((double)x1, (double)y1, (double)x2, (double)y2, c);
}
/**
* 線を描画するための内部メソッドです。再帰関数を使用しています。
* 再帰関数の例を示すために、このような実装としました。アルゴリズムの質は良くないです。
* @param x1 起点 X座標
* @param y1 起点 Y座標
* @param x2 終点 X座標
* @param y2 終点 Y座標
* @param c 文字
*/
private void drawLine(double x1, double y1, double x2, double y2, char c) {
this.drawPoint((int)x1, (int)y1, c);
this.drawPoint((int)x2, (int)y2, c);
if(Math.abs(x2 - x1) < 1.0 && Math.abs(y2 - y1) < 1.0) {
; // 何もしない
} else {
double x3 = (x1 + x2) / 2.0;
double y3 = (y1 + y2) / 2.0;
// 再帰呼び出し(2分岐)
this.drawLine(x1, y1, x3, y3, c);
this.drawLine(x3, y3, x2, y2, c);
}
}
このメソッドは直線を描画します。と言っても、「点をたくさん描画して直線に見せる」というだけです。このアルゴリズムでは、2点の中点を計算し、その左側半分と右側半分のそれぞれについて、再び中点を計算し～、と繰り返すことで、直線を描画します。
今の時点ではソースコードの細かいところまで理解する必要はありません。まだ学習していないことがたくさんありますから。ただ、引用したソースコードの 33行目、34行目が「2分岐する再帰関数」の肝心の部分になる、ということについては理解できるでしょうか。
2分岐する再帰関数のその他の例は以下の通りです。
指定文字で塗りつぶすメソッド fillを見ていきます。MyCanvas.javaの 207行目以降を以下に抜粋します。
/**
* 指定文字で塗りつぶします。カンバス外を指定した場合は何もしません。
* @param x X座標
* @param y Y座標
* @param c 文字
*/
public void fill(int x, int y, char c) {
if(c == this.canvas[y][x]) {
; // 指定座標の文字と描画文字が同じ場合は何もしない
} else {
try {
this.fill(x, y, c, this.canvas[y][x]);
} catch(ArrayIndexOutOfBoundsException e) {
; // 何もしない
}
}
}
/**
* 指定文字で塗りつぶすための内部メソッドです。再帰関数を使用しています。
* @param x X座標
* @param y Y座標
* @param toChar 置換後の文字
* @param fromChar 置換前の文字
*/
private void fill(int x, int y, char toChar, char fromChar) {
this.drawPoint(x, y, toChar);
// 再帰呼び出し(4分岐)
if(x > 0 && this.canvas[y][x - 1] == fromChar) {
this.fill(x - 1, y, toChar, fromChar);
}
if(x < this.width - 1 && this.canvas[y][x + 1] == fromChar) {
this.fill(x + 1, y, toChar, fromChar);
}
if(y > 0 && this.canvas[y - 1][x] == fromChar) {
this.fill(x, y - 1, toChar, fromChar);
}
if(y < this.height - 1 && this.canvas[y + 1][x] == fromChar) {
this.fill(x, y + 1, toChar, fromChar);
}
}
このメソッドは指定文字で塗りつぶします。と言っても、「点をひとつずつ描画して塗りつぶす」というだけです。このアルゴリズムでは、ある点の上下左右の4方面に注目し、その 4方面それぞれについて、再び上下左右の 4方面に注目し～、と繰り返すことで、塗りつぶしを実現します。
今の時点ではソースコードの細かいところまで理解する必要はありません。まだ学習していないことがたくさんありますから。ただ、引用したソースコードの 31行目、34行目、37行目、40行目が「4分岐する再帰関数」の肝心の部分になる、ということについては理解できるでしょうか。
4分岐する再帰関数は平面(2次元空間)上で何か処理をする場合によく使用されます。例えば、以下のような場合に使用することができます。
分岐する数が不特定の再帰関数もあります。例えば、以下のような場合に再帰関数を使用することができます。