再帰のループ展開その３

どんどん行こう。
昨日までで、なんとなくd をパラメータとしたループになりそうだと分かる。
各段階の計算結果はreturn_value のd - 1 の場所に格納していけば良い。
ということで、その見込みに従いd に対する操作を追加してみよう。

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

これでループにまとめても、d の値に応じて処理が進みそうな感じになった。
ところで、ここから更に展開しようとすると、どうしてもi による多重ループをなんとかしないといけないことに気づく。
ということでi も各呼び出し段階ごとに確保してみる。
各段階のi はそれぞれi[d - 1] で置き換えることができる。

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

今日はここまで。いよいよ、次回はi のループを消して、一つのループにまとめてみたい。