当我通过堆栈推送较少数据时，为什么我的堆栈会溢出？

Question

我正在创建加权美国地图，我已将邮政编码分解为 3 位邮政编码区。然后我使用 for 循环迭代 1000 次来为每个 3 位数字的拉链区域涂上随机颜色。

这每次都没有问题。如果我开始我的 for 循环计数超过 310，我当前的问题就会出现。任何小于 310 的东西都会完美循环。因此，由于增加初始计数意味着运行递归代码更少，所以这对我来说确实有意义。

调用for循环的代码：

private void GUI()
{       
    JFrame frame = new JFrame();
    frame.setLayout(new MigLayout());

    try
    {
        mapImg = ImageIO.read(new File("Res/Zipzone map of the US.png"));
    } 
    catch (IOException e) 
    {
        e.printStackTrace();
    }
    g = mapImg.createGraphics();

    for(int i = 311; i < 1001; i++)
    {
        Random rand = new Random();
        String count = "";
        int red = rand.nextInt(220) + 25;
        int green = rand.nextInt(220) + 25;
        int blue = rand.nextInt(220) + 25;
        if(i < 100)
        {
            count = "0" + i;
        }
        else
        {
            count = i + "";
        }
        if(i <= 512)
        {
            ApplyColor(count, new Color(red, blue, green));
        }
        else if( i > 909)
        {
            ApplyColor3(count, new Color(red, blue, green));
        }
        else
        {
            ApplyColor2(count, new Color(red, blue, green));
        }
    }

    frame.add(new JLabel("", new ImageIcon(GetScaledImage(new ImageIcon(mapImg).getImage(), 1400, 875)), JLabel.CENTER), "GROW, PUSH");
    frame.setTitle("US Map");
    frame.setSize(1500,900);
    frame.setLocationRelativeTo(null);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setVisible(true);
}

应用颜色功能的小例子：

private void ApplyColor(String zip, Color color)
{
    int x;
    int y;
    if(zip.equals("010"))
    {
        try
        {
            x = 3339;
            y = 672;
            FloodFill(x, y, new Color(mapImg.getRGB(x, y)), color);
            x = 3361;
            y = 681;
            FloodFill(x, y, new Color(mapImg.getRGB(x, y)), color);
        }
        catch(AWTException e)
        {
            e.printStackTrace();
        }
    }
}

以及 FloodFill 函数：

public void FloodFill(int x, int y, Color targetColor, Color replacementColor) throws AWTException
{
    if(new Color(mapImg.getRGB(x, y)).equals(replacementColor))
    {
        return;
    }

    g.setColor(replacementColor);
    g.fillRect(x, y, 1, 1);

    if(new Color(mapImg.getRGB(x-1, y)).equals(targetColor))
    {
        FloodFill(x-1, y, targetColor, replacementColor);
    }

    if(new Color(mapImg.getRGB(x+1, y)).equals(targetColor))
    {
        FloodFill(x+1, y, targetColor, replacementColor);
    }

    if(new Color(mapImg.getRGB(x, y-1)).equals(targetColor))
    {
        FloodFill(x, y-1, targetColor, replacementColor);
    }

    if(new Color(mapImg.getRGB(x, y+1)).equals(targetColor))
    {
        FloodFill(x, y+1, targetColor, replacementColor);
    }
}

Answer 1

我真的不知道为什么当你从 310 或更多开始时收到这个错误，因为你的代码中处理你所指的 "zip codes" 的部分太奇怪了，无法尝试理解，因为在任何情况下，理解它都不会使网站的任何其他访问者受益，只有你。

我怀疑正在发生的事情是，从 310 或以上开始，邮政编码的排列使得您的递归洪水填充算法需要比不这样做时做更多的绘画。

这让我们想到了您的递归洪水填充算法。

这不是进行洪水填充的正确方法。

这在学术界可能被认为是正确的，但在现实世界中却并非如此。

如果您的算法要绘制一长串像素，它将对每个像素进行递归。在您的初始化代码中，我看到您将框架的宽度设置为 1500，而在其他地方我看到您使用超过 3000 的坐标，这意味着您实际上给了您的算法很长的像素来绘制。这意味着它会递归很多。这就是你得到堆栈溢出异常的原因。

要纠正您的问题，您需要重写递归洪水填充算法，使其不会递归太多。例如，不是每次访问左侧的像素时都递归，只要有要绘制的像素就让它向左循环，并且只递归每个绘制像素上方的像素和下方的像素。这同样适用于访问右侧的像素。这是将算法的递归深度降低几个数量级的简单方法。

它还有一个好处是执行得更好，因为一旦你知道了你需要在一行中绘制的所有像素，你就可以用一个绘图调用来绘制它们，而不是执行一个 fillRect() 每像素。我们在这里谈论的是数量级的性能提升。

如果这还不足以解决您的堆栈溢出问题，那么您可能需要考虑将您的算法替换为使用堆栈数据结构而不是实际调用自身的算法。将递归算法转换为使用堆栈数据结构的非递归算法，您可以查找并找到大量解决方案。

当我通过堆栈推送较少数据时，为什么我的堆栈会溢出？

Why is my stack overflowing when I push less data through it?

java

recursion

graphics

paint