Eine Rekursion in eine Iteration in Java verwandeln?

Question

Ich erhalte einen Stapelüberlauffehler aufgrund meiner Rekursion, die eine Endlosschleife erzeugt. Das Verwandeln der Methode in eine Iteration würde dies stoppen, aber ich habe keine Ahnung wie!

Kann mich jemand anleiten, meine Rekursion in eine Schleife zu verwandeln?

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

Es ist speziell das return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);, was den Fehler verursacht!

Answer 1

Ihr rekursiver Aufruf befindet sich in der Endposition. Somit beschreibt es bereits eine Schleife. Ich muss es nur syntaktisch explizit machen:

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;
  }
}

Ich codiere nicht in Java. Wenn der obige Code in irgendeiner Weise nicht konform ist, betrachten Sie ihn bitte als Pseudocode und ändern Sie ihn in einen geeigneten Code.

Answer 2

Ihre Funktion wird niemals zurückkehren, wenn sie arr[startPos]nicht nulldurchgehend ist. Sie müssen eine Bedingung wie folgt stellen:

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);
}