0

以下のメソッドを反復から再帰に変更するにはどうすればよいですか?

public int[] pascal(int[] previous) 
{

    //The row is 1 element longer than previous row
    int[] row = new int[previous.length + 1];

    //The first and last numbers in row are always 1
    row[0] = 1;
    row[row.length - 1] = 1;

    //The rest of the row can be calculated based on previous row
    for (int i = 1; i < row.length-1; i++) 
    {
        row[i] = previous[i-1] + previous[i];
    }

    return row;
}
4

2 に答える 2

1

計算の「状態」は、パラメーターを介して渡す必要があります。したがって、int[] previous行だけでなく、より多くのパラメーターが必要になります。

通常、2 つのメソッドが必要です。よりシンプルなインターフェイスを備えたパブリック メソッドと、実際に計算を実行するプライベート メソッドです。

あなたの例では、これらの 2 つのメソッドは次のようになります。

public int[] pascal(int[] previous) { ... call the next overload ... }
private int[] pascal(... all the state needed ...) { ... recursive call or return the value ... }

最も簡単な方法の 1 つは、計算される新しい行と、再帰関数のパラメーターとして計算する必要がある次の位置のインデックスを渡すことです。したがって、次のようになります。

private int[] pascal(int[] previous, int currentIndex, int[] row) { ... }

現在、再帰関数には通常 2 つ (またはそれ以上) のケースがあります。これには、次の 2 つのケースがあります。

  • 「currentIndex」が、計算する必要がある最後のインデックスを過ぎている場合は、完了です。現在の行を返すだけです。
  • それ以外の場合は、現在のインデックスの値を計算し、それを行に入れ、計算を続行する再帰呼び出しを行います (終了したと判断するか、計算して再度呼び出すことにより、...)

これらの 2 つのケースをコーディングしましょう。

private int[] pascal(int[] previous, int currentIndex, int[] row) {
  if (currentIndex == previous.length) {
    return row;
  } else {
    // do some part of the calculation
    // and make a recursive call that would continue the calculation:
    return pascal(previous, ????, row);
  }
}

これが再帰関数の構造である理由がわかりますか?

わかりました、実際の計算に進みます:

private int[] pascal(int[] previous, int currentIndex, int[] row) {
  if (currentIndex == previous.length) {
    return row;
  } else {
    int currentValue = previous[currentIndex - 1] + previous[currentIndex];
    row[currentIndex] = currentValue;
    return pascal(previous, currentIndex, row);
  }
}

計算が行われます。次に、「より単純な」関数に適切なパラメーターを使用して再帰関数を呼び出させる必要があります。

public int[] pascal(int[] previous) {
  int rowSize = previous.length + 1;
  int[] row = new int[rowSize];
  row[0] = 1;
  row[rowSize - 1] = 1;
  return pascal(previous, 1, row);
}

それでおしまい。

ご覧のとおり、「トリック」はパラメーターに「状態」を保持することです。ここでは、元のループcurrentIndexと同じです。int ifor

于 2013-02-26T07:09:50.580 に答える
0

現在プログラムされているため、必要なものを取得するには、関数を何度も呼び出す必要があります。

再帰関数はそれ自体を呼び出します。このようにして、必要なものを取得するために一度だけ呼び出すことができます。

三角形の特定の行が 1 つだけ必要だと思います。関数に渡す必要がある唯一のパラメーターは、行番号です。

その関数が既にプログラムされており、特定の行番号 N-1 に対して呼び出すことができると想像してください。前の関数を使用して行 N を計算する関数を作成できますか?

ここで、最初の行とおそらく負の行番号というコーナーケースに注意してください。

とはいえ、この関数を使用して行ごとに三角形を表示するのは非常に非効率的です!

于 2013-02-26T07:11:00.400 に答える