4.5 再帰処理

ある関数から別の関数を呼び出す方法は、これまで説明したとおりです。ところで、関数内で自分自身を呼び出した場合はどうなるのでしょう。このような、関数内で自分自身を呼び出すようなことを再帰処理と呼びます。例えば、次のような関数を考えてください。

void Function() {
	Function();
}

Function() 関数は、自分自身を関数内で呼び出しています。この場合は永遠と自分を呼び出してしまうため、無限ループと化します。

再帰を利用することによって、特殊なループを作成することができます。しかし、多くのことは再帰を使用しなくとも、繰り返し文で可能です。そのため、再帰を使用するのは極まれなケースです。なぜならば、関数呼び出しは繰り返し文で作成した繰り返し処理よりも遅いからです。再帰は一部のアルゴリズムを簡素化するのに用いられることがあります。

#include <stdio.h>

void Function(int , int);

int main() {
	Function(0 , 10);
	return 0;
}

void Function(int iCount , int iMax) {
	if (iCount < iMax) {
		printf("Count = %d\n" , iCount);
		Function(iCount + 1 , iMax);
	}
}

実行結果

コード1は、再帰処理の利用法を理解するための簡単なプログラムです。再帰処理を利用した関数 Function( ) は、第一引数にカウンタの初期値を指定し、第二引数に最大値を指定します。Function() 関数は、iCount が iMax 以下であれば、Function(iCount + 1 , iMax) というように、カウンタをインクリメントし、自分自身を呼び出しています。

これを繰り返すことによって、iCount はいつか iMax に達し、Function() 関数は次々と制御を返し、最終的に呼び出し元まで復帰するという仕組みになっています。このほかにも、再帰処理を使った技術としては、関数 A() が関数 B() を呼び出し、関数 B() が関数 A() を呼び出すという相互再帰という関係も考えらます。

void FunctionA() {
	FunctionB();
}

void FunctionB() {
	FunctionA();
}

再帰処理を実用するケースは多くはありませんが、木構造の様なデータの解析や検索などに応用されます。