C言語編 第53章 再帰

先頭へ戻る

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

再帰呼び出し

この章では、再帰というプログラミングスタイルを説明します。

再帰というのは、あるものの中に、自分自身への参照が含まれていることをいいます。 例えば、ディレクトリの中にディレクトリが現れるような構造は、再帰的であると言えます。

ここで取り上げるのは、関数における再帰です。 つまり、ある関数が、自分自身を呼び出すというもので、これを再帰呼び出し(リカーシブコール)と言います。 次のような関数があるとしたら、これは再帰呼び出しをしています。

void func(void)
{
	puts( "Hello" );
	func();  /* 自分自身を呼び出す */
}

構文としては何も難しいことはなく、いつもどおりに関数呼び出しを行うだけです。 ただ、上記のような関数だと、何度も func関数を呼び出し続けてしまい、終わることがありません。
再帰呼び出しの難しさの1つがここにあります。 再帰呼び出しを行う場合には、どこかで再帰を打ち切るようにする必要があるのです。 例えば、次のようにすると、n回の再帰呼び出しで打ち切ることができます。

void func(int count)
{
	if( count <= 0 ){
		return;
	}

	puts( "Hello" );
	
	func( count - 1 );  /* 自分自身を呼び出す */
}

func関数に引数を追加し、何回再帰呼び出しをさせるかを指定できるようにしました。 再帰呼び出しの際には、この回数指定を -1 してから渡すようにすることで、再帰のたびに引数の値が減っていきます。 0以下が渡されると、関数の先頭にある if文が真となり、それ以上再帰呼び出しを行わずに return します。
実際に完全なプログラムで試すと、確かにうまく動作することが分かります。

#include <stdio.h>

void func(int count);

int main(void)
{
	func( 10 );  /* 10回再帰させる */

	return 0;
}

void func(int count)
{
	if( count <= 0 ){
		return;
	}

	puts( "Hello" );
	
	func( count - 1 );  /* 自分自身を呼び出す */
}

実行結果

Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello

何となく感じたかも知れませんが、再帰という手法は、本質的には繰り返し処理です。 つまり、「関数自体が繰り返される」というイメージです。
ですから、再帰で出来ることは、通常の繰り返し処理の手法で実現できます。 「関数自体が」を「while文全体が」といったように置き換えて考えてみると納得できるでしょうか。

ほとんどの場合、同じことを実現するのなら、再帰を使わない方が処理は効率的になります。 一方で、適切な場面で再帰を使うと、コードの記述が非常に簡潔になり、理解しやすいプログラムになります。
使いどころは難しいですが、1つ言えることは、再帰を使うべきか、使わないべきかをよく比較検討すべきだということです。 先ほどのサンプルプログラムなどは明らかに、再帰を使わない方が効率的ですし、理解もしやすいでしょう。


ここで当然ながら、再帰を使うことが有効な実例を挙げるべきなのですが、本章ではあえてそれはせず、全体的な概要だけ取り上げることにします。 というのも、ほとんどがアルゴリズムの話になってくるので、それは専用に用意しているアルゴリズムとデータ構造編で取り上げたいからです。

スタックオーバーフロー

ここで少し、関数呼び出しの仕組みを整理しておきましょう。

定義された変数が、メモリ上のどこかに配置されているのと同様、関数もメモリ上に置かれています。
関数の場合、その中身はコードの集まりですから、コード量に応じて消費するメモリ領域の大きさも変わってきます。 ただし、ここでいうコード量とは、C言語での記述量とはさほど関係なく、コンパイルされた後のマシン語での量のことです。 (コンパイルやマシン語の意味合いについては、以前、第24章で説明しています) 関数がメモリ上に置かれているからこそ、関数ポインタ(第37章)が実現できます。

関数を呼び出すという行為は、結局のところ、関数ポインタの実現方式と変わりはなく、 関数の置かれているメモリアドレスへジャンプしているだけです。 関数がメモリ上のどのアドレスにあるかは、コンパイルを行ったときに確定できるようになっています。

関数を呼び出し、関数内の処理の実行を終えたら、元の位置に戻ってこられる必要があります。 これについても、元の位置(関数呼び出しを行った地点でのメモリアドレス)をどこかに記憶しておくだけのことではありますが、 記憶しておくための場所が必要です。 そのために通常、コールスタックという仕組みが使用されます。

コールスタックは、スタックというデータ構造になっています。 このデータ構造は、机の上に本を積み上げていくようなイメージで、データを積み上げていくと考えられます。 取り出せるデータは、一番上にあるもの(=一番最後に積んだもの)だけです。
関数の呼び出し元の位置を記憶することを考えると、関数が更に関数を呼ぶケースがありますから、 そのたびに記憶も積み上げていかないといけない訳です。 そのため、スタックのような構造が適しています。 関数を呼ぶときに元の位置を積んでおき、関数を抜け出すときに取り出して、その位置へジャンプすれば元の位置に戻ってこられます。

問題なのは、コールスタックとして使うメモリ領域にも当然、限界があるということです。 この大きさを超えるような量をスタックに積もうとすると、スタックオーバーフローを引き起こします。 スタックオーバーフローが起きると、一般的にプログラムは強制終了します。
スタックの大きさは、VisualC++ ではデフォルトで 1MB、 Xcode (OS X) の場合、デフォルトは 8MB です。

VisualC++ の場合は、プロジェクトのプロパティから、[構成プロパティ] -> [リンカー] -> [システム] を選択して、 [スタックのサイズの設定] に 0x1000000 のように入力することで、スタックサイズを変更できます。
Xcode の場合は、Project の BuildSettings にある [Other Linker Flags] に、 「-Wl,-stack_size,0x1000000」のように入力します。
この場合、0x1000000 = 16MB になります。

コールスタックとして使われている領域は、元の位置を記憶すること以外に、渡された引数のための領域や、 関数内で定義されたローカル変数を置くための領域としても消費されます
ですから、再帰呼び出しが膨大な回数に渡って行われるようなプログラムは、スタックオーバーフローを引き起こす可能性が高くなります。 また、呼び出し回数が少なくても、非常に巨大なローカル変数を定義している場合、領域を一気に消費することになるので、 同様に、スタックオーバーフローの危険があります。

スタックオーバーフローを防ぐために取れる手段としては、以下のようなものが考えられます。

関数呼び出しが深くなり過ぎないようにといっても、必要なときはどうしても必要です。 そういう場合には、スタックサイズ自体を大きく取るようにしなければならないでしょう。

ローカル変数だけでなく、引数が巨大な場合でもスタックオーバーフローが起こる可能性はありますが、 引数が巨大というケースは、普通はあまり考えられません。 恐らく、構造体変数を渡そうとしていると思われますが、その場合はポインタを渡せば済むことです。

ローカル変数によって大量に消費されるというケースでは、 動的なメモリ割り当て(第34章第35章参照)を行うように変更するという手段も考えられます。
動的なメモリ割り当ての場合、ヒープ領域という場所が使用されますから、スタック領域の方は消費されなくなります。 この方法は、スタック領域を使わなくなる訳ですから、有効な解決策となります。
ただし、動的なメモリ割り当ては、ヒープ領域の不足などの要因によって失敗する可能性があることを考慮しなければなりません。

末尾再帰の除去

関数の中で、一番最後に実行される文が、再帰呼び出しになっている場合、それを末尾再帰と呼びます。 例えば、次のような再帰関数は末尾再帰になっています。

void func(int num)
{
	if( num < 0 ){
		return;
	}

	printf( "%d\n", num );
	--num;
	func( num );  /* 一番最後の文が、再帰呼び出し */
}

末尾再帰になっている関数は必ず、再帰を使わない形に変形できることが証明されています
処理効率の面から言えば、再帰を使わない方が、関数呼び出しのコストが節約でき、使用するスタック領域も削減できます。 そのため、再帰しない形に変形できることは覚えておくと良いでしょう。

末尾再帰の関数の形をよく観察すると、関数全体が while文の { } のように見えてくるでしょうか。 そのような感覚で捉えられれば、再帰を使わない形に変形できそうなのが分かるかと思います。
つまり、while文における } の部分で再帰している訳ですから、再帰呼び出し部分を } に置き換え、 関数の先頭を { に置き換えるように考えれば良いということになります。 よって、先ほどの再帰していた func関数は、次のようにただの繰り返しに変形できます。

while( num >= 0 ){  /* 再帰版だと関数の先頭部分(再帰を終わらせるための条件判定を含む) */
	printf( "%d\n", num );
	--num;
}  /* 再帰版だと func( num ); だった部分 */


練習問題

問題@ 階乗を計算する再帰関数を作成して下さい。 また、再帰しない方法でも作成して下さい。

問題A 次のようなプログラム片があります。

#include <stdio.h>

struct Data_tag {
	int num;
	struct Data_tag* next;
};

static struct Data_tag gHead;

int main(void)
{
	struct Data_tag data00;
	struct Data_tag data01;
	struct Data_tag data02;

	gHead.num = 0;
	gHead.next = &data00;

	data00.num = 15;
	data00.next = &data01;

	data01.num = 30;
	data01.next = &data02;

	data02.num = 45;
	data02.next = NULL;


	return 0;
}

Data_tag構造体のアドレスを渡すと、NULLポインタに行き着くまで nextメンバを辿っていき、 その過程で numメンバの内容を出力する関数を作成して下さい。 再帰版、非再帰版をそれぞれ作成して下さい。


解答ページはこちら

参考リンク

再帰の技法
 -- 再帰の利用法をC言語で解説。
プログラミングの宝箱 アルゴリズムとデータ構造 第2版
 -- 再帰呼び出しの基礎に関する章がある。

更新履歴

'2015/8/30 Xcode (OS X) に対応。
スタックサイズの設定を変更する方法を、コラムとして追記。

'2011/7/9 新規作成。



前の章へ

次の章へ

C言語編のトップページへ

Programming Place Plus のトップページへ