ここでは、自分自身を呼び出すことを関数の再帰呼出しという。
int型配列に格納されたＮ個のデータ（ａ［０］～ａ［Ｎ－１］）を昇順に整列する。整列の手順は以下のとおりである。
①与えられたデータ列の中央附近のデータａ［2/N］を選ぶ。この値をｓとする。
②ｓを基準とし、ｓ以下のデータは左側に、ｓ以上のデータは右側になるようにデータ列を分割する。分割の手順は以下に示す。
１）左端のデータをａ［ｉ］（ｉ＝０）、右端のデータをａ［ｊ］（ｊ＝Ｎ－１）とする。
２）ａ［ｉ］から右へ向かって基準値ｓ以上のデータを探す。
３）ａ［ｊ］から左へ向かって基準値ｓ以下のデータを探す。
４）ｉ，ｊの値により以下の処理を行う。
ア）ｉ＜ｊの時ａ［ｉ］とａ［ｊ］とを交換し、２）から繰り返す。
イ）ｉ＝ｊの時ａ［０］～ａ［ｉ－１］はすべてｓ以下、ａ［ｊ＋１］～ａ［Ｎ－１］はすべてｓ以上となっており、データ列は２つに分割された。
ウ）ｉ＞ｊの時ａ［０］～ａ［ｊ］はすべてｓ以下、ａ［ｉ］～ａ［Ｎ－１］はすべてｓ以上となっており、データ列は２つに分割される。
③分割された左側のデータを同様に分割する。
④分割された右側のデータを同様に分割する。
⑤要素数が２つ以下になるまで分割を繰り返す。要素数が２つのときは、昇順になるようにデータを入れ替える。
関数名はsort()、渡される仮引数は、
pa：データが格納された配列のポインタ
ｎ：データの個数
［プログラムの作成］
/*-----------------------------------------------
クイックソート
-------------------------------------------------*/
vold sort(int *pa,int n)
/*pa：データ列（配列）へのポインタ*/
/*n:データの個数*/
{
int s; /*基準値*/
int i,j; /*添字*/
if(n<=2){ /*要素数２以上*/
if(n==2)
if(*pa>*(pa+1))swap(pa,pa+1); /*昇順にする*/
return;
｝
else{
s=*(pa+n/2); /*基準値の選択*/
i=-1; /*右から*/
j=n; /*左から*/
while(i<j){
while(*(pa+(++i))<s);
while(*(pa+(--i))>s);
if (i<j)swap(pa+i,pa+j);
｝
if(i==j){
sort(pa,i); /*左側*/
sort(pa+i+1,n-i-1); /*右側*/
｝
else{
sort(pa,i); /*左側*/
sort(pa+i,n-i); /*右側*/
｝
｝
｝
/*-----------------------------------------------
データの交換
-------------------------------------------------*/
vold swap(int *pa,int *pb)
｛
int t;
ta=*pa;
*pa=*pb;
*pb=t;
}
解説
【関数の再帰呼出し】 数学の漸化式のようにもとめた値を使って次の値を求めるときや、この例題のように同じ処理を範囲を変えて行いたい時、関数の再帰呼出しを用いると、直観的でスマートなプログラムを書くことができる。
再帰呼出しが行われると、渡された引数や関数内で定義されたオブジェクトなどは、新たな領域が確保され、呼出し側とはまったく切りはなされる。
【再帰からの脱出】 再帰呼出しでは、関数から自分自身を呼び出すため、再帰を脱出する条件が必ず必要である。そうしないと、永久に自分自身を呼び続けてしまう。再帰呼出しでは、一般に関数の形は以下のようになる。
Kansuu()
{
if(脱出条件){
脱出処理;
return;
}
else{
：
：
kansuu() ←再帰呼出し
：
}
}
練習問題へ選択メニューに戻る