如何将递归转化为迭代？

Question

我遇到了一个可怕的stackoverflowerror，我想这是由于我的深度递归引起的（调试器帮助我确定了这一点...）。有没有人可以指导我将我的递归转换为循环？

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

更具体地说，return find(getNextLocation(startPos, ++stepNum, key), key, stepNum); 会导致递归。

- Numerouso

Answer 1

我相信这可以帮助您到达那里：

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

“诀窍”在于将用于结束递归的条件放入循环条件中。请注意，由于您的算法不像其他递归算法一样以任何方式使用中间结果，因此翻译相当简单。这种方法并不总是适用于所有递归算法，有时您需要添加数据结构来保存中间结果。

- Petr Janeček

Answer 2

这似乎是等价的：

这似乎是等价的：

。

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

- tucuxi

---

太好了，谢谢！我仍然遇到stackoverflow错误，因为我还有一个递归方法要更改，但如果可能的话，我将自己尝试解决它！ - Numerouso