Превратить рекурсию в итерацию в Java?
Я получаю ошибку переполнения стека из-за того, что моя рекурсия создаёт бесконечный цикл. Превращение метода в итерацию остановило бы это, но я понятия не имею, как!
Может ли кто-нибудь помочь мне превратить мою рекурсию в цикл?
private int findEmpty(int startPos, int stepNum, String key) {
if (arr[startPos] == null) {
return startPos;
}
return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);
}
Именно return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);это вызывает ошибку!
Ответы
Ваш рекурсивный вызов находится в хвостовой позиции. Таким образом, он уже описывает петлю. Просто нужно сделать это синтаксически явным:
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;
}
}
Я не кодирую на Java. Если приведенный выше код каким-либо образом не соответствует требованиям, считайте его псевдокодом и заменяйте его на что-нибудь подходящее.
Ваша функция никогда не вернется, если arr[startPos]не будет null. Вам нужно поставить условие примерно так:
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);
}