Zamieniasz rekurencję w iterację w Javie?

Question

Otrzymuję błąd przepełnienia stosu z powodu mojej rekurencji tworzącej nieskończoną pętlę. Przekształcenie metody w iterację zatrzymałoby to, ale nie mam pojęcia, jak to zrobić!

Czy ktoś może mnie poprowadzić w przekształcaniu mojej rekursji w pętlę?

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

To właśnie return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);powoduje błąd!

Answer 1

Twoje wywołanie rekurencyjne jest w pozycji ogona. Zatem już opisuje pętlę. Wystarczy wyrazić to jasno, składniowo:

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

Nie koduję w Javie. Jeśli powyższy kod jest w jakikolwiek sposób niezgodny, potraktuj go jako pseudokod i zmień na coś odpowiedniego.

Answer 2

Twoja funkcja nigdy nie powróci, jeśli arr[startPos]nie zostanie nullzakończona. Musisz ustawić warunek taki jak:

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