再帰のループ展開その１

ということで、再帰呼び出しを今度はループに展開してみようと思う。
結構ややこしいので、順を追ってちまちまと開いていくことにする。
展開対象となるのは、以下のexpand関数である。
作業はまずJavaの方で行い、後にＣの方も類似の記述に改めることにする。

private static long expand(long array, int dim) {
  if(dim < 2)return array[0];
  long subarray = new long[(dim - 1) * (dim - 1)];
  long value = 0;
  for(int i = 0; i < dim; ++i) {
    int l = 0;
    for(int j = 0; j < dim; ++j){
      if(j != i){
        for(int k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k];
        ++l;
      }
    }
    if(i % 2 == 0){
      value += (array[i * dim] * expand(subarray, (dim - 1)));
    }else{
      value -= (array[i * dim] * expand(subarray, (dim - 1)));
    }
  }
  return value;
}

まずは、再帰呼び出しの部分を基準に、関数の中を区分する。
そのために、以下のような書き換えを行い、呼び出し部分を切り出す。

private static long expand(long array, int dim) {
  if(dim < 2)return array[0];
  long subarray = new long[(dim - 1) * (dim - 1)];
  long value = 0;
  for(int i = 0; i < dim; ++i) {
    int l = 0;
    for(int j = 0; j < dim; ++j){
      if(j != i){
        for(int k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k];
        ++l;
      }
    }
    long result = expand(subarray, (dim - 1));
    if(i % 2 == 0){
      value += (array[i * dim] * result);
    }else{
      value -= (array[i * dim] * result);
    }
  }
  return value;
}

次に、このロジックは多重ループになるので呼び出しとループの関係から処理を分けてみる。

(A)


  return array[0];

(B)


  long[] subarray = new long[(dim - 1) * (dim - 1)];
  long value = 0;

(C)


    int l = 0;
    for(int j = 0; j < dim; ++j){
      if(j != i){
        for(int k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k];
        ++l;
      }
    }

(D)


    long result = expand(subarray, (dim - 1));

(E)


    if(i % 2 == 0){
      value += (array[i * dim] * result);
    }else{
      value -= (array[i * dim] * result);
    }

上記の(A)〜(E)までに分けると、元の関数は以下のようになる。

private static long expand(long[] array, int dim) {
  if(dim < 2){
    (A)
  }else{
    (B)
    for(int i = 0; i < dim; ++i) {
      (C)
      (D)
      (E)
    }
    return value;
  }
}

まずはここまで。