リカーシブ・コール

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

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

階乗の計算

　数学の教科書にある「順列と組み合わせ」のところで出てくる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変数が必要となる。

例えば、連結リストで構成された座標値のリストがあるとしよう。座標を順に調べていって、