Transformando uma recursão em uma iteração em Java?

Question

Recebo um erro de estouro de pilha devido à minha recursão criando um loop infinito. Transformar o método em uma iteração iria parar isso, mas não tenho ideia de como!

Alguém pode me orientar para transformar minha recursão em um loop?

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

É especificamente return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);isso que causa o erro!

Answer 1

Sua chamada recursiva está na posição final. Portanto, ele já descreve um loop. Só preciso torná-lo explícito, sintaticamente:

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

Eu não codifico em Java. Se o código acima não for compatível de alguma forma, considere-o como um pseudocódigo e mude para algo adequado.

Answer 2

Sua função nunca retornará se arr[startPos]não estiver completa null. Você precisa colocar uma condição 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);
}