再帰からループへの変換
バイナリサーチを例に、再帰からループへの変換をしてみます。バイナリサーチは、(a[0]<=a[1]<=a[2]<=...a[n])の順に並んだ配列aに値vがあるかどうか検索するアルゴリズムです。調べる領域の最初(first)と最後(last)で平均のフロア((first+last)/2)の位置nextの要素を調べます。
vより小さければ、firstから今調べたところまでにvは無いことが分かります。なので、次回firstはnext+1にして、調べる領域を縮めることができます。逆の場合も同様です。これを繰り返すといずれ探している値のある要素に出会う(a[next]==v)か、firstがlastより大きくなり、存在しないことが分かります。今、言葉で言ったことをコードにすると次のようになるでしょう。ただし見つからない場合は-1を返すとします。
int binary_search_range_0(int first, int last, const int a[], const int v) { if(first > last) return -1; int next = (first + last)/2; if(a[next] == v) return next; else if(a[next] > v) return binary_search_range_0(first, next - 1, a, v); return binary_search_range_0(next + 1, last, a, v); } int binary_search_0(const int a[], const int v, const int size) { return binary_search_range_0(0, size-1, a, v); } #include<assert.h> void test(int (*search)(const int[],const int,const int)) { int a[6] = {1, 2, 3, 4, 5, 6}; assert(-1 == search(a, 0, 6)); for(int i = 0; i < 6; i++) assert(i == search(a, i+1, 6)); assert(-1 == search(a, 7, 6)); } void test(int (*search)(int, int,const int[], const int)) { int a[6] = {1, 2, 3, 4, 5, 6}; assert(-1 == search(0, 6, a, 0)); for(int i = 0; i < 6; i++) assert(i == search(0, 5, a, i+1)); assert(-1 == search(0, 5, a, 7)); }
binary_search_range_0は、少しの変更で関数の呼び出し部分と関数の仮パラメータを揃えることができます。こうした状態を厳密な末尾再帰と言うそうです。
//厳密な末尾再帰 int binary_search_range_1(int first, int last, const int a[], const int v) { if(first > last) return -1; int next = (first + last)/2; int e = a[next]; if(e == v) return next; else if(e > v) last = next - 1; else first = next + 1; return binary_search_range_1(first, last, a, v); }
厳密な末尾再帰な関数はwhile(true)で囲んで最後の関数呼び出しを消しても同じ処理をします。
int binary_search_range_2(int first, int last, const int a[], const int v) { while(true) { if(first > last) return -1; int next = (first + last)/2; int e = a[next]; if(e == v) return next; else if(e > v) last = next - 1; else first = next + 1; } } int binary_search_1(const int a[], const int v, const int size) { return binary_search_range_2(0, size-1, a, v); }
インライン化すれば、binary_searchは1つの関数で書けます。
int binary_search_2(const int a[], const int v, const int size) { int first = 0; int last = size - 1; while(true) { if(first > last) return -1; int next = (first + last)/2; if(a[next] == v) return next; else if(a[next] > v) last = next -1; else first = next + 1; } }
whileの中の条件に(first<= last)に変えて、ifを消すこともできます。
int binary_search_3(const int a[],const int v,const int size) { int first = 0; int last = size - 1; while(first <= last) { int next = (first + last)/2; if(a[next] == v) return next; else if(a[next] > v) last = next - 1; else first = next + 1; } return -1; }