Java 递归函数有时有效

Question

我已经运用了迄今为止所学到的知识，但仍然无法解决这个问题，所以决定来到这里。

BasicBlock 对象由整数引用，并保存对列表中更多 block 的“地址”的引用。我想获取它们引用的地址，并且我想递归地执行此操作。一个 BasicBlock 可以保存对 0 个或多个其他 block 的引用。

下面的递归函数 getFunctionReferences 不断返回堆栈溢出错误，但有时仍能正常工作。

Map<Integer,BasicBlock> blockList blockList = new TreeMap<Integer,BasicBlock>();

public HashSet<Integer> getAssociatedAddresses(int function) {
    HashSet<Integer> blockAddresses = new HashSet<Integer>();   
    getFunctionReferences(this.blockList.get(function),blockAddresses);
    return blockAddresses;
}

private void getFunctionReferences(BasicBlock block, HashSet<Integer> blockAddresses){ 
    for (int x : block.getAddressReferenceList()) {  
        blockAddresses.add(x);
        getFunctionReferences(this.blockList.get(x), blockAddresses);
    }
}

我知道我在这个调用中做错了什么，特别是因为没有基本情况。但我不知道在这样的循环中如何处理递归......我也不知道合适的基本情况。

非常感谢您的帮助。

谢谢

Answer 1

如果存在循环(例如， block 1 引用 block 2， block 2 引用 block 3， block 3 引用 block 1)，您将获得无限递归，导致 StackOverflowError。

为了避免这种情况，您可以利用您维护的已访问 block 的 HashSet。您可以简单地检查一个 block 是否已被访问，并避免再次进行递归调用:

private void getFunctionReferences(BasicBlock block, HashSet<Integer> blockAddresses){ 
    for (int x : block.getAddressReferenceList()) {  
        if (blockAddresses.add(x)) { // only make a recursive call if x wasn't already
                                     // in the Set
            getFunctionReferences(this.blockList.get(x), blockAddresses);
        }
    }
}