Welcome to the CSC Q&A, where you can get help (and share your knowledge) about computer science!

How can I prevent a Stack Overflow with large recursion calls?

+13 votes
I'm in the process of fine tuning the maze algorithm in our maze game program so that it works with very large mazes.  The algorithm that I coded is recursive, but doesn't have any reason to be memory intensive.  I am sending instances of the Point class every time a method is called.

Is there a way I can reduce the memory usage in a recursive algorithm?  Or... is there a way I can increase the stack size for method calls?
asked Apr 28, 2015 in Spring 2015 by Ethan Halsall (100 points)

5 Answers

+6 votes
Without seeing your code I believe you are having too many recursive calls, every recursive call taking up more space on the stack. If you can accomplish the same task with a loop, this should prevent the error because each execution of the loop does not take up more space on the stack. Please post the code that is recursive and I'll take a look.
answered Apr 28, 2015 by Ethan Wojcinski (100 points)
+6 votes
If your code is recursive and you are running out of memory, try to avoid initializing variables in the recursive loop. We might be of more help if we say the block of code causing the error
answered Apr 28, 2015 by Daniel Shultz (100 points)
+6 votes
I actually talked to Ethan about this in my office today, and we talked about how to make the code non-recursive.

It is always *possible* to change recursion into iteration (even when it isn't simple "tail recursion), by using your own stack data structure to keep track of the information that you need.  (In Java, a LinkedList will do nicely, since it has push(), peek(), and pop() methods).  It can be tricky though... but it is a good exercise in algorithm manipulation.
answered Apr 28, 2015 by Forrest Stonedahl (3,438 points)
+5 votes

So far, I'm not finding a whole lot about minimizing memory usage. I have found a couple resources that suggest tail recursion (where the method's recursive call is the last line of the method) helps to improve efficiency, but I also haven't seen any explanation of why that would be true.

I didn't find anything addressing increasing the stack size, but I did find a Stack Overflow answer about increasing heap size. Since you can increase the heap size, my guess is that there probably would be a similar value you can set to increase the stack size.

http://stackoverflow.com/questions/11275650/how-to-increase-heap-size-of-an-android-application

answered Apr 28, 2015 by Andrew Shearouse (100 points)
+5 votes
I ended up implementing the solution Dr. Stonedahl and I came up with.  Essentially, I replaced the recursion with a stack (linked-list) data structure.  I created an object to store all the data needed for each movement in the maze generation algorithm.  Instead of using the run-time stack, I use this stack data structure to push, peek, and pop objects depending on the position of the algorithm.  I believe that the recursive implementation (runtime stack) was faster than the further abstraction that is needed in the linked list and the objects, so I think it would be nice for time intensive tasks to be able to increase the size of the runtime stack to prevent the overhead caused by the abstraction.
answered May 4, 2015 by Ethan Halsall (100 points)
...