再帰のループ展開その４

では、i のループを消してみよう。
ループを度外視してi[ ] の初期化とインクリンメントを該当箇所にバラしてみる。

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

これでループは消えたが、これでは単に消してしまっているだけなので、実際の処理としては不味い。
消えたループは、全体のループとして書き換えないといけない。
ただその場合、再帰呼び出しの前後ではループの別々の回になるので、それらを区別する必要がある。
そこで、flg という変数を導入し、全体ループの中で再帰呼び出し前（flg == 0）と呼び出し後（flg == 1）を区別することにする。

long[ ][ ] array = new long[dim][ ];
long[ ] return_value = new long[dim];
int[ ] i = new int[dim];
int d = dim;
int flg = 0;
if(d < 2){
  return_value[d - 1] = array[d - 1][0];
  d++;
  flg = 1;
}else{
  if(flg == 0){
    if(i[d - 1] == 0){
      (B)
    }
    if(i[d - 1] < d){
      (C)
      d--;
      i[d - 1] = 0;
      if(d < 2){
        return_value[d - 1] = array[d - 1][0];
        d++;
        flg = 1;
      }else{
          if(i[d - 1] == 0){
            (B)
          }
          if(i[d - 1] < d){
            (C)
            d--;
            i[d - 1] = 0;
            if(d < 2){
              return_value[d - 1] = array[d - 1][0];
              d++;
              flg = 1;
            }else{
              if(flg == 0){
                if(i[d - 1] == 0){
                  (B)
                }
                if(i[d - 1] < d){
                  (C)
                  d--;
                  i[d - 1] = 0;
                }
              }else{
                if(i[d - 1] < d){
                  (E)
                  i[d - 1]++;
                }
                if(i[d - 1] == d){
                  return_value[d - 1] = value;
                  d++;
                }
              }
            }
          }
        }else{
          if(i[d - 1] < d){
            (E)
            i[d - 1]++;
          }
          if(i[d - 1] == d){
            return_value[d - 1] = value;
            d++;
          }
        }
      }
    }else{
      if(i[d - 1] < d){
      (E)
      i[d - 1]++;
    }
    if(i[d - 1] == d){
      return_value[d - 1] = value;
      d++;
    }
  }
}

これで全ての場合分けが終わったので、全体をループで囲み、多重化されている部分を一段にすると以下のように書ける。

long[ ][ ] array = new long[dim][ ];
long[ ] return_value = new long[dim];
int[ ] i = new int[dim];
int d = dim;
int flg = 0;
do {
  if(d < 2){
    return_value[d - 1] = array[d - 1][0];
    d++;
    flg = 1;
  }else{
    if(flg == 0){
      if(i[d - 1] == 0){
        (B)
      }
      if(i[d - 1] < d){
        (C)
        d--;
        i[d - 1] = 0;
      }
    }else{
      if(i[d - 1] < d){
        (E)
        i[d - 1]++;
        flg = 0;
      }
      if(i[d - 1] == d){
        return_value[d - 1] = value;
        d++;
        flg = 1;
      }
    }
  }
}while(d <= dim);

ここでは、終了条件を d <= dim にしている。
では今日はここまで。