再帰処理(再帰コール)とは、あるメソッド(関数)の中で、自分自身を呼び出すことを言う。 大抵のプログラミング言語で使用できる。
再帰を使うことにより、プログラムがスリムになるが、 その動作は初心者あるいは中級者でも理解しにくいことがある。
また、メソッド(関数)コールのオーバヘッドが生じるため、実行時間がかかったり、 メモリ不足に陥るケースもある。 再帰を使わず、for 文に置き換えた方がよい場合もある。
int binary_search(int ary[], int key, int imin, int imax) {
if (imax < imin) {
return KEY_NOT_FOUND;
} else {
int imid = imin + (imax - imin) / 2;
if (ary[imid] > key) {
return binary_search(ary, key, imin, imid - 1);
} else if (ary[imid] < key) {
return binary_search(ary, key, imid + 1, imax);
} else {
return imid;
}
}
}
階層ディレクトリ下のファイル名(パス名)の一覧表を得る再帰処理は比較的分かりやすく、 また、しばしば必要とする処理である。Java言語による例を下に示す。
import java.io.File;
public class ListFiles {
static void list(File file) {
if (file.isDirectory()) {
File[] subfiles = file.listFiles();
for (File subfile : subfiles) {
list(subfile); // 再帰処理
}
} else { // 終了処理：ファイル
System.out.println(file.toString());
}
}
public static void main(String[] args) {
list(new File( "c:/_www"));
}
}
このプログラムの実行例を下に示す。 ホームページのファイルを c:\_www に置いているとき、 新規作成または更新されたファイルをサーバーに FTP転送するときに使う。 この場合は、ディレクトリやファイルの時刻も調べる。 c:\_www に新しいサブディレクトリができたときは、FTPコマンドを送り、 サーバー側にもその新しいサブディレクトリを作成する。
FFFTPのミラーリングアップロードを使えば済むが、ファイル数が増えると 実行時間がかかる。
c:\_www\.htaccess c:\_www\algorithm\osm-landparser01.html c:\_www\algorithm\point_in_polygon01.html c:\_www\algorithm\recursive_call01.html c:\_www\algorithm\src\pointf_java.txt c:\_www\android_java\onview01.html [後略]
Ramer-Douglas-Peuckerアルゴリズム（またはDouglas-Peuckerアルゴリズム）は 下に示すように、再帰を用いて折れ線データを簡略化するものである[1]。
simplySection関数は線分 points[i]-points[j] の間引きを行う関数である。 許容誤差を epsilon とする。
線分 points[i]-points[j]と途中の点 points[k] との垂直距離を調べて、 その最大値を maxDistance とする。
この最大値が epsilon を超えなければ、全ての中間点は間引いて、処理は終わりである。
最大値が許容誤差を超える場合には、 この最大値を持った点 points[maxIndex] は間引かないことに決定する。 この点を境として、ふたつの線分 points[i]-points[maxIndex]および points[maxIndex]-points[j] に分けて、 それぞれについて simplySection関数を再帰コールする。
[C/C++言語]
// Returns the distance from point p to the line between p1 and p2
double perpendicular_distance(point_t p, point_t p1, point_t p2) {
double dx = p2.x - p1.x;
double dy = p2.y - p1.y;
double d = sqrt(dx * dx + dy * dy);
return fabs(p.x * dy - p.y * dx + p2.x * p1.y - p2.y * p1.x)/d;
}
void simplifySection(point_t *points, size_t i, size_t j, double epsilon) {
if ((i + 1) == j) return;
double maxDistance = -1.0;
size_t maxIndex = i;
for (size_t k = i + 1; k < j; k++) {
double distance = perpendicular_distance(points[k], points[i], points[j]);
if (distance > maxDistance) {
maxDistance = distance;
maxIndex = k;
}
}
if (maxDistance <= epsilon) {
for (size_t k = i + 1; k < j; k++) {
points[k].unused = true; // 間引く
}
} else {
simplifySection(points, i, maxIndex, epsilon);
simplifySection(points, maxIndex, j, epsilon);
}
}