current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.4 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 0 down vote favorite

I am working on a school assignment in java and i have come across an error i can't find an answer on. Somehow, when i call the gethit() method on an object returned by iterator.next() i get a stack overflow exception. I suspect because the gethit() method (in this specific case) calls on itself recursively. Even though, i think it is strange to get a stack overflow since the recursion only goes 2 or 3 levels deep and my objects don't use an excessive amount of memory.

The shoot() method that makes the first call of gethit()

public void shoot() {
    assert canHaveAsEnergy(energy - 1000);

    //Search the target position.
    Position laserPos = new Position(getPos().getX(), getPos().getY(), getPos().getBoard());
    do {
        long nextX = laserPos.getX() + new Double(orientation.getDirection().getX()).longValue();
        long nextY = laserPos.getY() + new Double(orientation.getDirection().getY()).longValue();
        laserPos.setX(nextX);
        laserPos.setY(nextY);
    } while (getPos().getBoard().canHaveAsPosition(laserPos) && (! getPos().getBoard().hasAsPosition(laserPos)));
    //Hit every entity on the target position. 
    for (Entity entity : getPos().getBoard().getAllEntitiesOn(laserPos)) {
        entity.getHit();
    }
    setEnergy(energy - 1000);
}

The getHit() method that recursively calls on itself.

public void getHit() {
    ArrayList<Position> neighbours = new ArrayList<Position>();
    Position northPos = new Position(getPos().getX(), getPos().getY() - 1, getPos().getBoard());
    Position eastPos = new Position(getPos().getX() + 1, getPos().getY(), getPos().getBoard());
    Position southPos = new Position(getPos().getX(), getPos().getY() + 1, getPos().getBoard());
    Position westPos = new Position(getPos().getX() - 1, getPos().getY(), getPos().getBoard());
    neighbours.add(northPos);
    neighbours.add(eastPos);
    neighbours.add(southPos);
    neighbours.add(westPos);

    for (Position pos : neighbours) {
        if (getPos().getBoard().hasAsPosition(pos)) {
            Iterator<Entity> iterator = getPos().getBoard().getAllEntitiesOn(pos).iterator();
            while (iterator.hasNext()) {
                //Somehow this gives a stack overflow error
                iterator.next().getHit();
            }
        }       
    }
    System.out.println(this.toString() + " takes a hit and explodes.");
    getPos().getBoard().removeAsEntity(this);
    terminate();
}
share|improve this question
    
"recursion only goes 2 or 3 levels deep" - are you sure about that? – Greg Hewgill Jul 25 '12 at 20:31
up vote 1 down vote accepted

Everytime you call iterator, that will call another iterator that will call another iterator, and so forth. Thus your stack overflow from infinite recursion due to every iterator calling 

iterator.next().gethit();

Each iterator will just make a new iterator that needs to go through, but you continue calling getHit() again and again, so you'll never complete any of the function calls.

share|improve this answer
up vote 1 down vote

  • iterator.next().getHit(); calls getHit() method and iteration starts again and it continues (recursive loop). Have a variable or terminating point to exit the recursive loop.

  • Whenever method being invoked, it pushes information to stack frame, on method completion stack frame will be removed. In your case there is no way for method completion and removal of stack frame, which generates StackOverFlowError

share|improve this answer
up vote 0 down vote

While implementing Recursion you should make sure that there is one termination call where the method doesn't call itself.

Now you assume that this recursion should stop as you are moving to neighbors and checking whether they are hit or not but when you see the calls... (this is what dry ran with initial position 2,2)

[Original]=>[P1],[P2],[P3],[P4]
**[2,2]**=>[2,1],[3,2],[2,3],[1,2]
[2,1]=>[2,0],[3,1],**[2,2]**,[1,1]
[3,2]=>[3,1],[4,2],[3,3],[2,2]
[2,3]=>[2,2],[3,3],[2,4],[1,3]
[1,2]=>[1,1],[2,2],[1,3],[0,2]

So here when you firstly compute 4 neighbors and call getHit() on it. The Source cell comes as a neighbor of any one of the neighbors and this is good enough to get into a endless recursion.

You can identify your values by putting in the following statement...

public void getHit() {
    System.out.println("[" + getPos().getX() + "," + getPos().getY() + "]");
    ....
}

The solution here is to keep a list of cells, pass it as parameter, which are visited and never visit them again. Hope this helps.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.