Mengubah rekursi menjadi iterasi di Java?
Saya mendapatkan kesalahan stack overflow karena rekursi saya membuat loop tak terbatas. Mengubah metode menjadi iterasi akan menghentikan ini, tetapi saya tidak tahu caranya!
Adakah yang bisa membimbing saya dalam mengubah rekursi saya menjadi satu lingkaran?
private int findEmpty(int startPos, int stepNum, String key) {
if (arr[startPos] == null) {
return startPos;
}
return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);
}
Ini secara khusus return findEmpty(getNextLocation(startPos, ++stepNum, key), stepNum, key);
yang menyebabkan kesalahan!
Jawaban
Panggilan rekursif Anda berada di posisi ekor. Jadi itu sudah menggambarkan sebuah loop. Hanya perlu membuatnya eksplisit, secara sintaksis:
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;
}
}
Saya tidak membuat kode di Java. Jika kode di atas tidak sesuai dengan cara apa pun, harap anggap sebagai kode samaran dan ubah menjadi sesuatu yang sesuai.
Fungsi Anda tidak akan pernah kembali jika arr[startPos]
tidak null
seluruhnya. Anda perlu memberikan kondisi seperti:
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);
}