Java 递归函数有时有效

Question

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

BasicBlock 对象由一个整数引用，并保存对列表中 'addresses' 个更多块的引用。我想获得他们所引用的地址，我想递归地做这件事。一个 BasicBlock 可以持有对 0 个或多个其他块的引用。

下面的递归函数 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

如果你有循环（例如，块 1 引用块 2，块 2 引用块 3，块 3 引用块 1），你将得到无限递归，导致 WhosebugError。

为避免这种情况，您可以利用您维护的 HashSet 访问块。您可以简单地检查一个块是否已被访问，如果是，则避免进行另一个递归调用：

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

Java 递归函数有时有效

Java Recursive function sometimes working

java

stack-overflow

recursion