（私がこれまでに書いた）方法で：
private int[] calculateSum(int[] array, int index) {
int[] result = new int[array.length];
if (index > 0) { //implicit break condition
calculateSum(array, index-1);
result[index] = array[index]+result[index-1]; //should be sum of array values up until array[index]
}
return result;
}
引数配列の要素に基づいて新しい配列にデータを入力し、新しい配列を返すことになっています。
しかし、部分的に入力された配列resultを前の再帰呼び出しに戻し続けるにはどうすればよいですか？このコードが実行resultされると、再帰呼び出しごとに新しい配列が作成されます。ヘルパーメソッド、グローバル変数、または定義されているメソッド以外のものは使用できません。
一般的に（そして最も重要なことですが）アキュムレータや追加の変数を使用できない場合、部分的/現在のソリューションを次のメソッド呼び出しに渡すにはどうすればよいですか？メソッド内に変数を作成すると、後続の再帰呼び出しごとに新しい変数が作成され、その値を前のフレームに渡すことができません。
もう1つの典型的な例は、次のとおりです。署名付きのメソッドのみを使用して、指定された整数のゼロの数を再帰的にカウントします。
int noZeroes(int x) {}
私が見つけたすべての情報源を含む。R.Sedgewick、ESRoberts、MTGoodrich etal。例では異なる「ヘルパー構造」を使用しているため、「限られた」リソースで再帰を処理する方法についての指示が見つかりません。
私はここで同じことを想定しi、想定しindexています。
不足しているのは、によって返される配列を使用していることcalculateSum(array, i-1)です。
アイデアは、再帰の最後に単一の配列を作成し、追加して、再帰呼び出しごとにその配列を変更し続けることです。
private int[] calculateSum(int[] array, int index)
{
if (index == 0) {
return Arrays.copyOf (array, array.length);
} else {
int[] result = calculateSum(array, index-1);
result[index] += result[index-1];
return result;
}
}
再帰の終わりに達すると、入力配列のコピーを作成します。それがあなたが返す配列です。次に、再帰呼び出しが返されるたびに、配列の1つの要素を変更します。
入力の場合：
{1,2,3,4,3}
このメソッドは以下を返します：
[1, 3, 6, 10, 13]
index == 0、元の配列のコピーを返します{1,2,3,4,3}。index == 1、次のように追加result[0]しresult[1]て返します{1,3,3,4,3}。index == 2、次のように追加result[1]しresult[2]て返します{1,3,6,4,3}。index == 3、次のように追加result[2]しresult[3]て返します{1,3,6,10,3}。index == 4、次のように追加result[3]しresult[4]て返します{1,3,6,10,13}。ところで、入力配列の変更が許可されている場合は、このメソッドをメソッドに変更できvoid、入力配列には次の結果が含まれます。
private void calculateSum(int[] array, int index) {
if (index > 0) {
calculateSum(array, index-1);
array[index] += array[index-1];
}
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加