equalsメソッドを再帰的に実装する

Question

基本的には、2つの配列を比較し、同じ位置に同じ値があるかどうかを確認する必要があります（もちろん再帰的です）。私は私の現在のコードでエラーを取得：配列をインデックス例外の外：20

次のように私は今見えているコード：

private boolean equalsHelper(int[] first, int[] second, int iStart, int iEnd){ 
    if (first[iStart] == second[iStart]){ 
     if (equalsHelper(first,second,(iStart+1),iEnd)) 
     { 
      return true; 
     } 
    } 
    if (iStart == iEnd){ 
     return first[iEnd] == second[iEnd]; 
    } 
    return false; 
} 

Answer 1

（それは本当にありませんが、ここでの反復は自明であるとパフォーマンスが向上します）再帰が適切なソリューションであるかどうかの質問をともかく、問題は、終了条件（iStart == iEndが）後までチェックされていないということです再帰呼び出し。

再帰アルゴリズムは、a）再帰を続行することが適切かどうかをチェックし、b）のチェックの後に再帰呼び出しを実行する必要があります。最初のステップを含めることができないか、順不同のステップを実行すると、エラーに達するまで無限に再帰します（最初に何も起こらなければStackOverflowError）。

再帰呼び出しの前に条件チェックがありますが、再帰を終了するのではなく、メソッドの全体的な目的に適しています。再帰を終了するための条件チェックもありますが、再帰呼び出しの後に実行されます。解決策は、注文を交換することです。if (iStart == iEnd)ブロックを取り出し、if (first[iStart] == second[iStart])ブロックの前に移動してください。

Answer 2

ますので、あなたの配列のサイズを過ぎて続けるでしょうあなたの方法チェックが必要です。

private boolean equalsHelper(int[] first, int[] second, int iStart, int iEnd) { 
    if(iStart >= first.length) return true; //reached end with no mismatch 
    // the rest of your code 

Answer 3

再帰は強力なプログラミング手法ですが、Java言語にはいくつかの欠点があります。 Javaのメソッドが繰り返し回帰的に呼び出すと、それを返す前に余分な回数だけStackOverflowErrorが発生します。このインスタンスは、2つのArrayの等価性を比較するとほぼ同等の結果が得られます。

Scalaのような他の言語では、再帰（末尾再帰）に最適化された再帰関数を記述し、定数スタック領域で実行することができます。

これまで、再帰が本当に正しい解決法であるかどうかを考える必要がありました。それは解決策を最適化したり、コードの明瞭性を追加することもありません。

注：：2つの配列をJavaで比較したい場合は、java.util.Arraysがすでに対象です。

Answer 4

コードの先頭に停止条件を設定するだけです。 iStartが先頭に0とiEndである場合、これは動作しますが、配列の長さである - あなたはほんの少しのコードを変更する必要がiEndための入力として、配列の長さを使用する場合は1

private boolean equalsHelper(int[] first, int[] second, int iStart, int iEnd) { 

    if (iStart == iEnd) { // you need to check this first 
     return first[iEnd] == second[iEnd]; 
    } 

    if (first[iStart] == second[iStart]) { 
     if (equalsHelper(first, second, (iStart + 1), iEnd)) { 
      return true; 
     } 
    } 
    return false; 
} 

private boolean equalsHelper2(int[] first, int[] second, int iStart, int iEnd) { 
    if (iStart == iEnd) { 
     return true; 
    } 

    if (first[iStart] == second[iStart]) { 
     if (equalsHelper2(first, second, (iStart + 1), iEnd)) { 
      return true; 
     } 
    } 
    return false; 
} 

パフォーマンスは数回述べられているので、私はそれについていくつか言います。 スタックには、ローカル変数と関数呼び出しに関する情報が含まれています。だから、各再帰呼び出しはスタックにこれらの情報を保存します。スタックは限られたスペースしか持たないので、膨大な入力に対してスタックオーバーフローが発生します。また、ループと比較してアセンブラコマンドが多くなるため、実行速度が遅くなります。

これは、テール再帰関数を使用することで回避できます。 テール再帰呼び出しとは、再帰呼び出しが、メソッドで最後に実行された文でなければならないことを意味します。コンパイラはこれをループに変換します。これは速く、スタックのスペースを少なくします。

あなたのequalsメソッドの末尾再帰バージョンは、次のようになります。

private boolean equalsHelper2(int[] first, int[] second, int iStart, int iEnd) 
{ 
    if (iStart == iEnd) 
    { 
     return true; 
    }else{ 
     if(first[iStart] != second[iStart]) 
     { 
      return false; 
     } else 
     { 
      return equalsHelper2(first, second, iStart + 1, iEnd); 
     } 
    } 
}