Java: Recursion causes Stack Overflow Error even though code is correct

Question

I am trying to make a program that goes through a sprite image, and then makes each shape in it a new image. For example, if we took Mario, I want the hat to be one image, the face to be another, and so on. I have gotten my program to work on small 32x32 images, but if I want to run this on a larger image, it causes a Stack Overflow Error. If I was using C++, I would just go about this by clearing the stack after each recursive call, but as far as I know, Java does not let you directly clear the stack. I want my program to run on Windows, Linux and Mac so I thought Java would be the best option, so I don't really want to switch the language I am using. Is there a way to delete whatever was stored on the stack after each recursive call in Java? Here is my code, just in case there is an error with it.

 private void makeShape(int x, int y)
    {
        if(x < 0 || y < 0 || y >= sprite.getHeight() || x >= sprite.getWidth())
        {
            return;
        }
        if(sample == colorData[y][x] && table[y][x])
        {
            tempBlankImage[y][x] = sample;
            table[y][x] = false;
            makeShape(x, y - 1);
            makeShape(x, y + 1);
            makeShape(x - 1, y);
            makeShape(x + 1, y);
        }
        else
        {
            return;
        }

    }

The x and y points are generated from a for loop that goes through the image and checks if a point has been added to a shape, and if not it makes a shape from its surrounding pixels.

UPDATE:

    private int[][] makeShape(int sample, int x, int y)
    {
        int[][] tempBlankImage = blankImage();
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(x,y));
        while(!queue.isEmpty())
        {
            Point point = queue.remove();
            if(sample == colorData[point.y][point.x] && table[point.y][point.x])
            {
                tempBlankImage[point.y][point.x] = sample;
                table[point.y][point.x] = false;
                if(point.y < sprite.getHeight() -1)
                    queue.add(new Point(point.x, point.y+1));
                if(point.y > 0)
                    queue.add(new Point(point.x, point.y-1));
                if(point.x < sprite.getWidth()-1)
                    queue.add(new Point(point.x+1, point.y));
                if(point.x > 0)
                    queue.add(new Point(point.x-1, point.y));
            }

        }
        queue = null;
        return tempBlankImage;
    }

The Stack Overflow Error has stopped, now I am getting out Out of Memory: Java Heap Space, even though I increased it to 2 GB. I am adding each int[][] to an ArrayList, which I am guessing is the issue. How else can I store the data?

This doesn't directly answer your question, but; any reason not to just use a nested loop, outer for x and inner for y? That would be simpler, and more efficient. (You could also do a single-dimension index, with one loop; each index is y*width + x). — yshavit
– yshavit, Commented Dec 17, 2015 at 2:38
I do have one in a different method, and it looks at the table array and once there is a cell that returns true, it calls makeShape — Jedi_Maseter_Sam
– Jedi_Maseter_Sam, Commented Dec 17, 2015 at 2:40
I'd suggest looking up iterative floodfill algorithm to avoid recursion — Christian R.
– Christian R., Commented Dec 17, 2015 at 2:55
What does "clearing the stack after each recursive call" mean? — Andreas
– Andreas, Commented Dec 17, 2015 at 3:21
Although the correct answer is certainly to write this iteratively rather than recursively, you may be able to avoid the stack overflow by swapping the second and third calls to makeShape, so that not every cell is on the stack at once. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Dec 17, 2015 at 7:10

m.antkowicz · Accepted Answer · 2015-12-17 02:41:35Z

1

Java is well known for it's automatic well defined and tested memory management system - it is generally not good idea to manage memory on your own even if it is possible (because in some level it actually is).

What will clearing stack give you if the alghoritm execution time will let you get a beard and be able to tell stories about it to your grand children?

Do not make it as recursive - think about some iterative form of an alghoritm. You can for example iterate over all image's pixels and add them to the appropriate image (due to it's color) that will be stored in some HashMap like in this pseudo code

    HashMap<Color, Image> images= new HashMap<Color, Image>();

    for(Pixel pixel : originImage)
        Color color = pixel.getColor();
        images.get(color).put(pixel)

Do not waste your life for bad code

answered Dec 17, 2015 at 2:41

m.antkowicz

13.7k22 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jedi_Maseter_Sam Over a year ago

If I did that, how would I go about separating the pixels by the ones that touch, so I can have all the shapes of a color on separate layers, instead of each layer containing all the shapes of the given color.

m.antkowicz Over a year ago

of course - it is only simple example - read about Flood fill alghoritm or Smith's alghoritm (not Smith–Waterman text alghoritm) - I had implemented this one somewhere and was good but it is hard to find implementation

Jedi_Maseter_Sam Over a year ago

I came up with something based on the Wiki, but now I run out of heap space.

Collectives™ on Stack Overflow

Java: Recursion causes Stack Overflow Error even though code is correct

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related