Transformer une récursion en une itération en Java?

Question

J'obtiens une erreur de dépassement de pile en raison de ma récursivité créant une boucle infinie. Transformer la méthode en une itération arrêterait cela, mais je ne sais pas comment!

Quelqu'un peut-il me guider pour transformer ma récursivité en boucle?

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

C'est précisément ce return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);qui cause l'erreur!

Answer 1

Votre appel récursif est en position de queue. Ainsi, il décrit déjà une boucle. Il suffit de le rendre explicite, syntaxiquement:

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

Je ne code pas en Java. Si le code ci-dessus n'est pas conforme de quelque manière que ce soit, veuillez le considérer comme un pseudocode et le changer en quelque chose d'approprié.

Answer 2

Votre fonction ne reviendra jamais si elle arr[startPos]n'est pas nullterminée. Vous devez mettre une condition comme:

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