1. 総当りプログラムの概要

N桁のM進数が取りうるすべての整数を出力します。

たとえば3桁の2進数なら、
{000, 001, 010, 011, 100, 101, 110, 111}
を出力します。

forループ1回で、1桁のM進数が取りうるすべての整数を出力できるので、
総当りプログラムをforループで書くと、実にN重ループのコードになってしまいます。

今回はそんな問題を、再帰構造にすることで綺麗にまとめてしまいましょう。

2. ソースコード

はじめにソースコードを提示します。
マクロの値を変えることで、パラメータを変更できます。

MAX_IDX : N桁
MAX_VAL : M進数
INIT : M進数の初期値(基本は0)

recursive_brute_force.c

#include <stdio.h>

#define MAX_IDX 2
#define MAX_VAL 1
#define INIT 0

void print_a(int* a){

	int i = 0;

	for (i = 0; i < MAX_IDX+1; i++){
		printf("%d ", a[i]);
	}
	printf("\n");

}

int check_init(int* a){

	int i;

	for (i = 0; i <= MAX_IDX; i++){
		if (a[i] != INIT) return 0;
	}

	return 1;

}

int recursive_increment(int idx, int* a){

	if (idx < MAX_IDX) {
		while (1){
			a[idx] += recursive_increment(idx + 1, a);
			if (a[idx] > MAX_VAL){
				a[idx] = INIT;
				return 1;
			}
			if (check_init(a)) break;
		}
		return 0;
	}
	else {
		print_a(a);
		if (a[idx] == MAX_VAL){
			a[idx] = INIT;
			return 1;
		}
		else{
			a[idx]++;
			return 0;
		}
	}

	return -1;
}

int main(void){

	int a[MAX_IDX + 1];
	int buf, i;
	
	for (i = 0; i < MAX_IDX + 1; i++){
		a[i] = INIT;
	}

	buf = recursive_increment(0, a);

	return 0;
}

3. 解説

上記のソース（recursive_brute_force.c）の詳細を説明します。

3.1. アプローチ

まずは簡単な例として、3桁の2進数を考えましょう。

冒頭に示したとおり、この場合に取りうる値は
{000, 001, 010, 011, 100, 101, 110, 111}
となります。

この集合を総当りで表示するには、次のアルゴリズムが考えられます。

取りうる最も低い値（000）で初期化する。2に進む。
1桁目をインクリメントする。3に進む。
1桁目が最大値(1)を超えたら、4に進む。そうでない場合、2に進む。
1桁目を初期値(0)にし、2桁目をインクリメントする。2桁目が最大値を超えたら、5に進む。そうでない場合、2に進む。
1桁目と2桁目を初期値にし、3桁目をインクリメントする。3桁目が最大値を超えたら、終了する。そうでない場合、2に進む。

当たり前と言えば当たり前ですが、このアルゴリズムが基本になります。
上の例では3桁の2進数と状況を限定しているので、手計算でも、forループでも簡単に計算できますが、
一般化するとなると少々難しくなります。

3.2. 再帰的に一般化

3.1.で示したアルゴリズムを再帰的に一般化すると、下記のようになります。

取りうる最も低い値で初期化する。桁を表わす変数idxを0で初期化する(idx=0は最上位桁)。2に進む。
idxが最下位桁を指していなければ、再帰する。idxをインクリメントし、再び2に進む。最下位桁なら、3に進む。
最下位桁の値が最大値なら、最下位桁を初期値にし、1を返す。それ以外なら、最下位桁をインクリメントし、0を返す。4に進む。
返り値をidx桁に足す。最大値を超えたら、idx桁を初期値にし、1を返して、再び4に進む。それ以外なら、5に進む。
すべての桁が初期値なら、0を返して、4に進む。

スタック上の関数がmain関数のみとなったとき、このアルゴリズムは終了します。

再帰をするたびにidxがインクリメントしてより低い桁を指すようになり、
再帰から返るたびに桁がひとつずつ上がっていく、というイメージが理解できれば、掴みやすいです。