How to avoid StackOverflowError for a recursive function

Question

I'm writing a function that will call itself up to about 5000 times. Ofcourse, I get a StackOverflowError. Is there any way that I can rewrite this code in a fairly simple way?:

void checkBlocks(Block b, int amm) {

    //Stuff that might issue a return call

    Block blockDown = (Block) b.getRelative(BlockFace.DOWN);
    if (condition) 
        checkBlocks(blockDown, amm);


    Block blockUp = (Block) b.getRelative(BlockFace.UP);
    if (condition) 
        checkBlocks(blockUp, amm);

    //Same code 4 more times for each side

}

By the way, what is the limitation of how deep we may call the functions?

http://stackoverflow.com/questions/214741/what-is-a-stack-overflow-error — Balaswamy Vaddeman, Apr 09 '12 at 13:01

score 21 · Accepted Answer · edited Aug 31 '18 at 12:51

Use an explicit stack of objects and a loop, rather than the call stack and recursion:

void checkBlocks(Block b, int amm) {
  Stack<Block> blocks = new Stack<Block>();
  blocks.push(b);
  while (!blocks.isEmpty()) {
    b = blocks.pop();
    Block blockDown = (Block) b.getRelative(BlockFace.DOWN);
    if (condition)
      blocks.push(block);
    Block blockUp = (Block) b.getRelative(BlockFace.UP);
    if (condition) 
      blocks.push(block);
  }
}

score 7 · Answer 2 · answered Apr 09 '12 at 13:05

default stack size in java is 512kb. if you exceed that program will terminate throwing StackOverflowException

you can increase the stack size by passing a JVM argument : -Xss1024k

now stack size is 1024kb. you may give higher value based on your environment

I don't think we can programmatically change this

score 0 · Answer 3 · answered Apr 09 '12 at 12:57

0

You can increase the stack size by using -Xss4m.

answered Apr 09 '12 at 12:57

Sandro

1,266
2
13
25

But what if the board size just keeps increasing? I think he realized this and did not ask how to increase the stack size, but rather how to refactor the code! – barsju Apr 09 '12 at 12:59

score 0 · Answer 4 · answered Apr 09 '12 at 12:58

0

You may put your "Block"s into a queue/stack and iterate as long as Blocks are available.

answered Apr 09 '12 at 12:58

stefan bachert

9,413
4
33
40

score 0 · Answer 5 · answered Apr 09 '12 at 13:00

It's obvious that you get StackOverflow with such branching factor of your recursion. In other languages it can be achieved by Tail Call Optimization. But I suppose your problem needs another way to solve.

Ideally, you perform some check on Block. Maybe you can obtain list of all blocks and check each of them iteratively?

zip · Answer 6 · 2012-04-09T15:11:15.297

In most cases recursion is used in a wrong way. You shouldn't get a stack over flow exception. Your method has no return type/value. How do you ensure your initial Block b is valid?

If you are using recursion, answer yourself the following question:

what is my recursion anchor (when do i stop with recursion)
what is my recursion step (how do I reduce my number of calculations)

Example:

n! => n*n-1!

my recursion anchor is n == 2 (result is 2), so I can calculate all results beginnging from this anchor.

my recursion step is n-1 (so each step I get closer to the solution (and in this fact to my recursion anchor))

How to avoid StackOverflowError for a recursive function

6 Answers6

Linked