How to turn recursion into iteration?

user_14730281 0
Viewed 91

I get a horrific stackoverflowerror, and figured it was my deep recursion causing it (well, the debugger helped with that...). Can anyone guide me in turning my recursion into a loop?

    H<V>.Pair currPair = (H<V>.Pair) arr[startPos];
    if (arr[startPos] == null) {
        return null;
    }

    if (currPair.key.equals(key)) {
        return currPair.value;
    } else {
        return find(gNL(startPos, ++stepNum, key), key, stepNum);
    }
}

More specifically, return find(getNextLocation(startPos, ++stepNum, key), key, stepNum); causes the recursion.

recursion iteration java
2 Answers

This seems to be equivalent:

private V find(int startPos, String key, int stepNum) {

    Hashtable<V>.Pair p;
    boolean finished = false;
    do {
       p = (Hashtable<V>.Pair) arr[startPos]; 
       if (p == null || p.key.equals(key)) {          
           finished = true;
       } else {
           startPos = getNextLocation(startPos, ++stepNum, key);
       }
    } while( ! finished);

    return p == null ? null : p.value;
}
user_154720

I believe this gets you there:

private V find(int startPos, String key, int stepNum) {
    Hashtable<V>.Pair currPair = arr[startPos];
    while ((currPair != null) && !currPair.key.equals(key)) {
        stepNum++;
        int nextPos = getNextLocation(startPos, stepNum, key);
        currPair = arr[nextPos];
    }

    return (currPair == null)
            ? null
            : currPair.value;
}

The "trick" is to put the conditions you used to end recursion into the loop condition. Note that because your algorithm doesn't use the intermediate results in any way as some other recursive algorithms do, the translation is quite straightforward. This will not work every time with all recursive algorithms, sometimes you'll need to add a data structure to hold your intermediate results.

user_12730800
Related