DOSプロンプト

若葉プログラミング塾 > 知識の玉手箱 > ワンポイントTips > Webサービス

リカーシブ・コール

　リカーシブとは、入れ子のことである。親亀の背中に小亀が乗って、小亀の背中に孫亀が…。と、無限に続く構造を指す。こういう構造のプログラムをリカーシブといい、実に美しい。亀よりマトリョーシカ人形の方が近いかも。どうせプログラミングをやるなら、リカーシブを知らないで済ませる手はない。

　しかしリカーシブを使うにはちょっとしたテクニックが必要なので、ここで階乗のプログラムを例に解説しておこう。

階乗の計算

　数学の教科書にある「順列と組み合わせ」のところで出てくるn!のことであるが、まだ学校で習っていない人のために式を書いておく。

 n! = n × (n-1) × (n-2) × … × 1

　つまり、３の階乗なら 3! = 3 × 2 × 1 = 6 となり、４の階乗なら 4! = 4 × 3 × 2 × 1 = 24 となるわけで、想像がつくと思うが、べき乗より早く大きくなっていく。

　任意の数ｎの階乗を求めるソースコードは例えばこんな風になる。

#include <stdio.h>
unsigned long factorial(int n);

void main() {
	int n;
	unsigned long ans;
	
	printf("階乗の計算：");
	scanf("%d", &n);
    
	ans = factorial(n);
	printf("%dの階乗=%lu\n", n, ans);
        
}

/* 階乗を求めるリカーシブ関数 */
unsigned long factorial(int n) {
	if (1 == n) return n;
	return n * factorial(n-1);
}

　ごらんのとおり、繰り返し計算なのに、while文もfor文も表れない。自分の中で自分を呼ぶことで、繰り返しを実現するのだ。

リカーシブの注意点

　リカーシブの第一の注意点は、終了判定の重要さだ。上記のコードで、if(1 == n)がなければ永遠に計算を続ける。一種の無限ループである。

　次に、無限リカーシブをやってみればわかるが、STACK OVERFLOWが出やすいことだ。関数へのパラメタはスタックに詰まれるので、ヒープ領域と異なり、サイズの上限が決まっている。コンパイル・リンク時にオプションでスタックサイズを大きくしておかないと、ロジックによってはすぐにSTACK OVERFLOWになってしまう。これはなにもリカーシブに限ったことではないが（階層の深い関数コールを多用すると起こり得る）、リカーシブは特にスタックを大量消費することに注意すべきである。

static変数の意味

　さて、階乗の計算は、ロジックが入れ子なのでリカーシブの使用が適していた。他にも、ハノイの塔の問題や、 C言語コース教科書で扱っている連結リストの削除などに使えるが、リカーシブ・コールの特徴として、「値を覚えておけない」というやっかいな問題がある。リカーシブ関数は呼ばれるたびに状況が変化しており、前回呼ばれたときの値を覚えておくためには、static変数が必要となる。

例えば、連結リストで構成された座標値のリストがあるとしよう。座標を順に調べていって、①と③を結ぶ線上に②があった場合、 ②を削除してリストを繋ぎかえる関数を作るとき、リカーシブを使うならば、下記のようなロジックになる。(直線判定部は省略)

typedef struct COOD {
	float x, y;
	struct COOD *next;
} COOD;

void shortcut(COOD *cood) {
	COOD *next, *next2;
	float a1, a2, b1, b2;
	
	next = cood->next;
	next2 = next->next;
	if (!next2) return;	/* 2つ先がなければ終了 */
	
	if(/* 直線上だったら */) {
		cood->next = next2;
		free(next);
		shortcut(cood);	/* 再処理*/
	}
	else {
		shortcut(next);	/* 次の座標にいく */
	}
}

　しかし、これが閉じている図形だったらどうだろう。最後の座標のnextは、最初の座標を指している。終了条件がなく、ぐるぐる回ってしまう。そういうときにstatic変数の出番である。

void shortcut(COOD *cood) {
	COOD *next, *next2;
	static COOD *start = NULL;
	
	if (!start) start = cood;	/* 先頭座標の記憶 */
	
	next = cood->next;
	if (next == start) return;	/* 先頭に戻ったら終了 */
	next2 = next->next;
	
	if(/* 直線上だったら */) {
		cood->next = next2;
		free(next);
		shortcut(cood);	/* 再処理*/
	}
	else {
		shortcut(next);	/* 次の座標にいく */
	}
}

　static変数を使わないでこれを実現するには、パラメタに常に「先頭座標」を渡さねばならないが、リカーシブでこれをやってはいけない。上述のとおりスタックは限られており、リカーシブ・コールにおいては貴重品なのである。たった一つの値を共有するのに、毎回スタックを消費するのは、無駄遣いもいいところだ。必要最小限のものだけパラメタで渡す、それが極意である。

リカーシブ・コール

若葉プログラミング塾 > 知識の玉手箱 > ワンポイントTips > Webサービス