Java Recursive function sometimes working

Question

I've called upon what I've learned so far and still can't fix this so decided to come here.

A BasicBlock object is referenced by an integer and holds references to the 'addresses' of more blocks in a list. I want to obtain the addresses that they hold reference to and i thought to do this recursively. It is possible for one BasicBlock to hold reference to 0 or more other blocks.

The below recursive function getFunctionReferences keeps returning a stack overflow error, yet manages to work sometimes.

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

I know that I am doing something wrong with this call, especially as there is no base case. But I don't know how to deal with recursion when it is in a loop like this....nor do I know a suitable base case.

Help massively appreciated.

Thanks

Answer 1

If you have cycles (for example block 1 references block 2 which references block 3 which references block 1), you'll get infinite recursion leading to StackOverflowError.

To avoid that, you can take advantage of the HashSet of visited blocks which you maintain. You can simply check if a block was already visited and avoid making another recursive call if it was:

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