Javaで再帰を反復に変えますか？

Question

再帰によって無限ループが発生するため、スタックオーバーフローエラーが発生します。メソッドを反復に変えるとこれは止まりますが、どうすればよいかわかりません。

誰かが私の再帰をループに変えるように私を導くことができますか？

private int findEmpty(int startPos, int stepNum, String key) {
    if (arr[startPos] == null) {
        return startPos;
    }
    return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);
}

特にそれがreturn findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);エラーの原因です！

Answer 1

再帰呼び出しはテール位置にあります。したがって、それはすでにループを記述しています。構文的に明示的にする必要があります。

private int findEmpty(int startPos, int stepNum, String key) {
  while( True ) 
  {
    if (arr[startPos] == null) {
        return startPos;
    }
    // return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);
    ++stepNum;
    int nextPos = getNextLocation(startPos, stepNum, key);
    // return findEmpty(nextPos, stepNum, key);
    startPos = nextPos;
  }
}

私はJavaでコーディングしていません。上記のコードが何らかの形で準拠していない場合は、それを擬似コードと見なして、適切なものに変更してください。

Answer 2

が完全arr[startPos]でない場合、関数は決して戻りませんnull。次のような条件を設定する必要があります。

private int findEmpty(int startPos, int stepNum, String key) {
    if (startPos == arr.length) {
        return -1; // The value if no null element is found
    }
    if (arr[startPos] == null) {
        return startPos;
    }
    return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);
}