¿Convertir una recursividad en una iteración en Java?

Question

Recibo un error de desbordamiento de pila debido a que mi recursividad crea un bucle infinito. Convertir el método en una iteración detendría esto, ¡pero no tengo idea de cómo!

¿Alguien puede guiarme para convertir mi recursividad en un bucle?

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

¡Es específicamente lo return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);que causa el error!

Answer 1

Tu llamada recursiva está en posición de cola. Por tanto, ya describe un bucle. Solo necesito hacerlo explícito, sintácticamente:

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

No codifico en Java. Si el código anterior no es compatible de alguna manera, considérelo como un pseudocódigo y cámbielo por algo adecuado.

Answer 2

Su función nunca volverá si arr[startPos]no está completa null. Necesita poner una condición algo como:

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