再帰のループ展開その２

では展開の続きを。
次に(B)の部分とreturn文をループの中に入れることが出来るので入れておく。
ただし、i に関する条件付きで。

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

さて、ここからが本番である。
関数の呼び出しの記述によって簡略化されている要素を取り出して実装していかなければならない。
とりあえずは再帰呼び出しの部分(D)の部分を、何段か実際に埋め込んで必要な変数を見つけるための考察を行う。
実際には文法に反しているのでコンパイルできないが、以下のようになる。

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

これから分かるのは、関数の返り値と引数はそれぞれの呼び出し毎に別のものを確保しておけば良さそうだということだろう。
ただ、int dim はそれぞれの呼び出しを区別するパラメータとして使っているだけなので、制御変数として一つ確保しておけば良さそうだ。
ということで、以下のように書き換える。

long[ ] array = new long[dim][ ];
long return_value = new long[dim];
int d = dim;
//d = dim
if(d < 2){
  (A)
}else{
  for(int i = 0; i <= d; ++i) {
    if(i == 0){
      (B)
    }
    if(i < d){
      (C)
      //d = dim - 1
      if(d < 2){
        (A)
      }else{
        for(int i = 0; i <= d; ++i) {
          if(i == 0){
            (B)
          }
          if(i < d){
            (C)
            //d = dim - 2
            if(d < 2){
              (A)
            }else{
              for(int i = 0; i <= d; ++i) {
                if(i == 0){
                  (B)
                }
                if(i < d){
                  (C)
                  //d = dim - 3
                  //以下省略
                  //d = dim - 2
                  (E)
                }
                if(i == d){
                  return_value[d - 1] = value;
                }
              }
            }
            //d = dim - 1
            (E)
          }
          if(i == d){
            return_value[d - 1] = value;
          }
        }
      }
      //d = dim
      (E)
    }
    if(i == d){
      return_value[d - 1] = value;
    }
  }
}

ここで、(A)が以下のように書き換わることに気づく。

(A)


  //d = 1
  return_value[d - 1] = array[d - 1][0];

これはもう、埋め込んでしまおう。
すると、こうなる。

long[ ] array = new long[dim][ ];
long return_value = new long[dim];
int d = dim;
//d = dim
if(d < 2){
  //d = 1
  return_value[d - 1] = array[d - 1][0];
}else{
  for(int i = 0; i <= d; ++i) {
    if(i == 0){
      (B)
    }
    if(i < d){
      (C)
      //d = dim - 1
      if(d < 2){
        //d = 1
        return_value[d - 1] = array[d - 1][0];
      }else{
        for(int i = 0; i <= d; ++i) {
          if(i == 0){
            (B)
          }
          if(i < d){
            (C)
            //d = dim - 2
            if(d < 2){
              //d = 1
              return_value[d - 1] = array[d - 1][0];
            }else{
              for(int i = 0; i <= d; ++i) {
                if(i == 0){
                  (B)
                }
                if(i < d){
                  (C)
                  //d = dim - 3
                  //以下省略
                  //d = dim - 2
                  (E)
                }
                if(i == d){
                  return_value[d - 1] = value;
                }
              }
            }
            //d = dim - 1
            (E)
          }
          if(i == d){
            return_value[d - 1] = value;
          }
        }
      }
      //d = dim
      (E)
    }
    if(i == d){
      return_value[d - 1] = value;
    }
  }
}

これで、return文が無くなった。ループへの展開に一歩近づいたと言える。
では今日はここまで。