関数の再帰呼び出し

自分を呼び出す関数

関数は、その処理の中で自分自身を呼び出すことができます。
これを再帰呼び出し(再帰処理)と言います。

再帰呼び出しの具体例

具体的な例をみてみましょう。

#include <stdio.h>

int factorial(int n)
{
    if (n == 0)
        return 1;

    return n * factorial(n > 0 ? n - 1 : -n - 1);
}

int main()
{
    int number = 6;
    int ret = factorial(number);

    printf("%dの階乗: %d", number, ret);

    getchar();
}

これはある整数の階乗を求めるサンプルコードです。

階乗とは、1からある整数までの整数をすべて乗算(掛け算)をした数のことです。
例えば6の階乗(6!と記述する)は、
「6 × 5 × 4 × 3 × 2 × 1 = 720」
となります。

上のコードでは、関数factorialの中で、自分自身である関数factorialが再度使用されています。
これが再帰呼び出しです。

このコードの呼び出しは順番に、

• 6 * factorial(5);
• 6 * (5 * factorial(4));
• 6 * (5 * (4 * factorial(3)));
• 6 * (5 * (4 * (3 * factorial(2))));
• 6 * (5 * (4 * (3 * ( 2 * factorial(1)))));
• 6 * (5 * (4 * (3 * ( 2 * (1 * factorial(0))))));

のようになります。
(ちなみに0の階乗は1です)

再帰呼び出しの注意点

再帰呼び出しは上手く使えばコードが簡潔に書けることもあります。
しかし以下に示すようなデメリットもあります。

無限ループ

再帰呼び出しは一種のループ処理ですので、無限ループが発生する危険があります。
必ず終了条件を設定し、適切にループを終了させる必要があります。

速度面のコスト

関数の呼び出しには多少のオーバーヘッド(実行コスト)があります。
最近のパソコンでは処理時間は大した問題にはなりませんが、forなどの普通のループ文では発生しないコストです。

メモリの枯渇

関数を呼び出すと、引数やローカル変数などでメモリが消費されます。
これらはスタックというメモリ上の領域に保存されます。
実はプログラムひとつ当たりで使用できるスタック領域はそれほど大きくありません。
そのため、大量に関数を呼び出すとメモリが足りなくなる場合があります。
(スタックオーバーフローという)

再帰呼び出しは、自分自身を終了させる前に再び自分自身を呼び出す処理です。
百回ループする再帰呼び出しを行うと、最終的に百個の関数が同時実行状態になります。
引数やローカル変数の値は関数が終了するまでは破棄されませんから、このような状態になるとメモリの使用量が一時的に膨大になり、スタックオーバーフローが発生する可能性があります。

これを避けるには、再帰呼び出しをやめてwhileなどのループ文に置き換えるのが確実です。
一度ずつ関数を終了させればメモリは破棄されますから、スタックオーバーフローの危険性はありません。

例えばある数値の階乗を返す関数ならわざわざ再帰を使用する必要はなく、単純なループ文で実現できます。

int factorial2(int n)
{
    if (n == 0)
        return 1;

    char sign = 1;
    if (n < 0) {
        sign = -1;
        n = -n; //符号を反転
    }

    int total = n;
    while (--n > 0)
    {
        total *= n;
    }    

    return total * sign;
}

行数は多くなってしまいますが、大きな数値を引数に与えてもコード上で宣言した変数と引数ひとつ分しかメモリを消費しないので、こちらのほうがメモリ使用量は大幅に少なくなります。

木構造データの走査

再帰呼び出しが効果的である典型例は木構造(ツリー構造)のデータに対するアクセスです。
例えばディレクトリ構造は木構造で作られています。
あるディレクトリ(フォルダ)内のファイルやディレクトリすべてにアクセスする場合に再帰呼び出しがよく用いられます。

以下は再帰呼び出しでサブディレクトリ(ディレクトリ内のディレクトリ)内のファイルも含めて一覧表示するサンプルコードです。
ただし、使用しているdirent.hというヘッダファイルはLinuxには存在しますが、Windows版のVisual Studioには存在しません。
使用している関数やマクロの詳細な説明は省きます。

//このコードはVisual Studio + Windows環境ではおそらく動作しません

#include <stdio.h>
#include <string.h>
#include <dirent.h>
#include <sys/stat.h>

//path1とpath2を/で結合してpathに格納
void combinePath(char *path, const char *path1, const char *path2)
{
    strcpy(path, path1); //バッファオーバーランに注意
    strcat(path, "/");
    strcat(path, path2);
}

//ディレクトリpath内のファイルをサブディレクトリも含めて表示
//サブディレクトリ内のファイルはindent文字分字下げする
void ListAllFiles(const char *path, int indent)
{
	char path2[256];

	//ディレクトリオブジェクト
    DIR *dir;
	
	//ディレクトリ内の次のエントリ(ファイルやサブディレクトリ)の情報
    struct dirent *entry;
	
	//ファイル情報を保存する構造体
	struct stat st;
	
	//ディレクトリを開く
    dir = opendir(path);
    if (dir == NULL) {
		return;
	}

	//ディレクトリから次のエントリを取り出し
	//NULLが返ると終了
	while((entry = readdir(dir)) != NULL) {
		//「.」から始まる名前は無視
		if(*(entry->d_name) == '.')
			continue;

		//字下げ(インデント)
		for(int n = 0; n < indent; n++)
			printf(" ");

		//エントリからファイル名を取得
		printf("%s", entry->d_name);

		//パスの結合
		combinePath(path2, path, entry->d_name);

		//エントリの情報を取得
		stat(path2, &st);

		//ディレクトリの場合
		if (S_ISDIR(st.st_mode)) {
			printf("/\n");
			//ListAllFiles関数を再帰呼び出し
			ListAllFiles(path2, indent + 1);
		}
		else{
			printf("\n");
		}
	}

	//ディレクトリを閉じる
	closedir(dir);
}

int main()
{
	//カレントディレクトリ内の「abc」という
	//ディレクトリ内のファイルを一覧表示
	ListAllFiles("abc", 0);
    return 0;
} 

a/
 a1.txt
 a2.txt
 a_sub/
  a_sub1.txt
  a_sub2.txt
b/
 b1.txt
 b2.txt
c.txt

ファイルのリストアップ程度であればメモリが足りなくなるほどの再帰呼び出しが行われることはありません。
また、forなどのループ文で記述するよりも簡潔に書くことができます。