Превратить рекурсию в итерацию в Java?

Nov 29 2020

Я получаю ошибку переполнения стека из-за того, что моя рекурсия создаёт бесконечный цикл. Превращение метода в итерацию остановило бы это, но я понятия не имею, как!

Может ли кто-нибудь помочь мне превратить мою рекурсию в цикл?

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);это вызывает ошибку!

Ответы

3 WillNess Nov 29 2020 at 23:09

Ваш рекурсивный вызов находится в хвостовой позиции. Таким образом, он уже описывает петлю. Просто нужно сделать это синтаксически явным:

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. Если приведенный выше код каким-либо образом не соответствует требованиям, считайте его псевдокодом и заменяйте его на что-нибудь подходящее.

LiveandLetLive Nov 29 2020 at 23:14

Ваша функция никогда не вернется, если 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);
}