递归中的堆栈溢出

Question

我正在制作一种 MS Paint 应用程序，它绘制轮廓并填充内部。我编写了填充轮廓的递归函数。它工作正常，但如果conture太大，程序会抛出stackoverflow异常。我该如何解决这个问题？我什至无法捕捉到这个异常((

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Runtime.InteropServices;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {

[DllImport( "user32.dll" )]
static extern IntPtr GetDC( IntPtr hWnd );
[DllImport( "user32.dll" )]
static extern int ReleaseDC( IntPtr hWnd, IntPtr hDC );
[DllImport( "gdi32.dll" )]
static extern int GetPixel( IntPtr hDC, int x, int y );
[DllImport( "gdi32.dll" )]
static extern int SetPixel( IntPtr hDC, int x, int y, int color );

static public Color GetPixel( Control control, int x, int y )
{
    Color color = Color.Empty;
    if (control != null)
    {
        IntPtr hDC = GetDC( control.Handle );
        int colorRef = GetPixel( hDC, x, y );
        color = Color.FromArgb(
            (int)(colorRef & 0x000000FF),
            (int)(colorRef & 0x0000FF00) >> 8,
            (int)(colorRef & 0x00FF0000) >> 16 );
        ReleaseDC( control.Handle, hDC );
    }
    return color;
}
static public void SetPixel( Control control, int x, int y, Color color )
{
    if (control != null)
    {
        IntPtr hDC = GetDC( control.Handle );
        int argb = color.ToArgb();
        int colorRef =
            (int)((argb & 0x00FF0000) >> 16) |
            (int)(argb & 0x0000FF00) |
            (int)((argb & 0x000000FF) << 16);
        SetPixel( hDC, x, y, colorRef );
        ReleaseDC( control.Handle, hDC );
    }
}

        int oldX, oldY;
        public Form1()
        {
            InitializeComponent();
        }



        private void button1_Click(object sender, EventArgs e)
        {
            Graphics g = panel1.CreateGraphics();
            g.Clear(panel1.BackColor);
        }
        bool paint;

        private void Form1_Load(object sender, EventArgs e)
        {

        }

        private void panel1_MouseDown(object sender, MouseEventArgs e)
        {
            oldX = e.X;
            oldY = e.Y;
            paint = true;
        }

        private void panel1_MouseUp(object sender, MouseEventArgs e)
        {
            paint = false;
        }

        private void panel1_MouseMove(object sender, MouseEventArgs e)
        {
            if (paint)
            {
                Graphics g = panel1.CreateGraphics();
                Pen p = new Pen(Color.Black);
                g.DrawLine(p, oldX, oldY, e.X, e.Y);
                oldX = e.X;
                oldY = e.Y;
            }
        }

        private void panel1_MouseDoubleClick(object sender, MouseEventArgs e)
        {
            fill(e.X, e.Y, Color.Black, Color.Red);
            Color c = GetPixel(panel1, e.X, e.Y);
            ClearButton.BackColor = c;
            label1.Text = e.X + " " + e.Y;

        }
        private void fill(int x, int y, Color border, Color c) {

            Color PointedColor = GetPixel(panel1, x, y);

            try { 
                        if (PointedColor.R != border.R && PointedColor.G != border.G && PointedColor.B != border.B &&
                PointedColor.R != c.R && PointedColor.G != c.G && PointedColor.B != c.B &&
                x >= 0 && x < panel1.Size.Width && y >= 0 && y < panel1.Size.Height)
            {
                SetPixel(panel1, x, y, c);

                fill(x - 1, y, border, c);
                fill(x + 1, y, border, c);
                fill(x, y - 1, border, c);
                fill(x, y + 1, border, c);

            }

            }
            catch(System.StackOverflowException e)
            {
                label1.Text = e.Message;
            }

        }
    }
}

Answer 1

您应该使用非递归洪水填充算法。

有关说明，请参阅维基百科文章

Bob Powell 有一些源代码这里。

请注意，尝试通过每次创建新线程来解决当前堆栈溢出的问题是一个非常昂贵的解决方案：采用简单的非递归解决方案绝对是更好的方法。创建额外的线程来解决堆栈问题并不是线程的正确使用方式。如果您认为通过使用多个线程可以获得更好的性能，即使这样您也应该采用非递归解决方案。

Answer 2

您不能捕获 StackOverflowException 按设计：

<块引用>

从 .NET Framework 2.0 版开始，try-catch 块无法捕获 StackOverflowException 对象，并且默认情况下会终止相应的进程。因此，建议用户编写代码来检测和防止堆栈溢出。例如，如果您的应用程序依赖于递归，请使用计数器或状态条件来终止递归循环。

我确信有更有效的方法可以实现这一目标。但是，首先，您可以通过将调用堆栈具体化为 Stack 将递归转换为迭代：

private void fill(int xInitial, int yInitial, Color border, Color c) 
{
    var remaining = new Stack<Tuple<int, int>>();
    remaining.Push(Tuple.Create(xInitial, yInitial));

    while (remaining.Any())
    {
        var next = remaining.Pop();
        int x = next.Item1;
        int y = next.Item2;

        Color PointedColor = GetPixel(panel1, x, y);

        if (PointedColor.R != border.R && 
            PointedColor.G != border.G && 
            PointedColor.B != border.B &&
            PointedColor.R != c.R && 
            PointedColor.G != c.G && 
            PointedColor.B != c.B &&
            x >= 0 && 
            x < panel1.Size.Width && 
            y >= 0 && 
            y < panel1.Size.Height)
        {
            SetPixel(panel1, x, y, c);
            remaining.Push(Tuple.Create(x - 1, y));
            remaining.Push(Tuple.Create(x + 1, y));
            remaining.Push(Tuple.Create(x, y - 1));
            remaining.Push(Tuple.Create(x, y + 1));
        }
    }
}