再帰からループへの変換

バイナリサーチを例に、再帰からループへの変換をしてみます。バイナリサーチは、(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;
}