Catching "Stack Overflow" Exceptions in Recursive C++ Functions

Catching stack overflow

Off the top of my head, one way to catch excessive stack growth is to check the relative difference in addresses of stack frames:

#define MAX_ROOM    (64*1024*1024UL)    // 64 MB

static char *   first_stack = NULL;

void foo(...args...)
{
    char    stack;

    // Compare addresses of stack frames
    if (first_stack == NULL)
        first_stack = &stack;
    if (first_stack > &stack  &&  first_stack - &stack > MAX_ROOM  ||
        &stack > first_stack  &&  &stack - first_stack > MAX_ROOM)
        printf("Stack is larger than %lu\n", (unsigned long)MAX_ROOM);

    ...code that recursively calls foo()...
}

This compares the address of the first stack frame for foo() to the current stack frame address, and if the difference exceeds MAX_ROOM it writes a message.

This assumes that you're on an architecture that uses a linear always-grows-down or always-grows-up stack, of course.

You don't have to do this check in every function, but often enough that excessively large stack growth is caught before you hit the limit you've chosen.

C#: Exception handling in recursive call

I think you are trying to include the recursive path in the exception details so as to aid debugging.

What about trying this.

public void Recursive(int x)
{
  try
  {
    _Recursive(x)
  }
  catch
  { 
    throw new RecursionException(path.ToString(), ex);
    clear path, we know we are at the top at this point
  }
}

private void _Recursive(int x)
{
    // maintain the recursion path information
    path.Push(x);

    _Recursive(x + 6);

    //maintain the recursion path information
    //note this is not in a catch so will not be called if there is an exception
    path.Pop()
}

If you are using threading etc, you will may have to look at storing path in thread local storage.

---

If you don’t wish to force your caller to deal with RecursionException, you could make the “path” public so the caller can access it. (As par Eric Lippert later answer)

Or you could log the path to your error logging system when you catch the exception and then just re-throw the exception.

public void Recursive(int x)
{
  try
  {
    _Recursive(x)
  }
  catch
  { 
    //Log the path to your loggin sysem of choose
    //Maybe log the exception if you are not logging at the top 
    //   of your applicatoin         
    //Clear path, we know we are at the top at this point
  }
}

This has the advantage that the caller does not need to know about the “path” at all.

It all comes down to what your caller needs, somehow I think you are the caller for this code, so there is no point us trying to 2nd guess what is needed at this level of deal.

Stack overflow exception error in a recursive function

You're not keeping track of which spaces you've already visited. So supposing your grid has two zeros right next to each other, your function will move to one in the first level of recursion, then to the other in the second level, then back to the first in the third level (even though the first level of recursion is still on the stack) and so forth forever.

There are a number of ways that you could keep track of where you've already visited. If you're willing to modify the input array temporarily when this method is called, you could just set the space you're currently on to 1 before looking at the ones around it.

    public static int recursiveCheck(int[,] grid,int x, int y, int finalX, int finalY, int paths)
    {
        var originalValue = grid[x, y];
        if (originalValue == 6)
        {
            paths++;
            return paths;
        }
        grid[x, y] = 1; // prevent deeper recursion from coming back to this space
        if ((grid[x + 1, y] != 1) && (x+1 < finalX))
            return recursiveCheck(grid, x + 1, y, finalX, finalY, paths);
        if ((grid[x, y+1] != 1) && (y+1 < finalY))
            return recursiveCheck(grid, x, y+1, finalX, finalY, paths);
        if ((grid[x - 1, y] != 1) && (x > 0))
                return recursiveCheck(grid, x - 1, y, finalX, finalY, paths);
        if (grid[x, y - 1] != 1 && y >0)
                return recursiveCheck(grid, x, y - 1, finalX, finalY, paths);

        grid[x, y] = originalValue; // allow other path checking to revisit this space.

        return 0;
    }

Also note that you can probably simplify things a little bit by turning the recursion upside down a little: do your boundary checks and wall checks as exit criteria right away, and use the number of paths purely as a return value rather than an input.

public static int recursiveCheck(int[,] grid, int x, int y, int finalX, int finalY)
{
    if(x < 0 || x > finalX || y < 0 || y > finalY)
    {
        return 0;
    }
    var originalValue = grid[x, y];
    if (originalValue == 1)
    {
        return 0;
    }
    if (originalValue == 6)
    {
        return 1;
    }
    grid[x, y] = 1; // prevent deeper recursion from coming back to this space
    var paths = recursiveCheck(grid, x + 1, y, finalX, finalY)
        + recursiveCheck(grid, x, y + 1, finalX, finalY)
        + recursiveCheck(grid, x - 1, y, finalX, finalY)
        + recursiveCheck(grid, x, y - 1, finalX, finalY);

    grid[x, y] = originalValue; // allow other path checking to revisit this space.

    return paths;
}

Trying to catch a failed allocation inside of a recursive function: Unhandled exception/Stack overflow

You have to distinguish between two kinds of exceptions: hardware exception and software exception. C++ exception can be considered as a software exception, so using C++ try/catch statement you can catch only software exceptions. An example of software exceptions is when program detects that invalid parameter has been specified for some procedure.

Hardware exceptions are far more serious and are thrown by CPU itself. Example of hardware exception are: division by zero, trying to access an invalid memory address, stack overflow and others. Many of these hardware exceptions are handled by operating system itself (debuggers also process some of these exceptions) and it is strongly recommended not to catch these exceptions in your program. Doing so you might prevent lower level systems to properly clean-up the mess that was left behind.

So back to stack overflow that you're having trouble with, when this hardware exception happens the stack pointer has exceeded the stack bound. In other words, your program is out of stack (this is over-simplification because each thread in the process gets certain amount of stack space so it might be that only thread ran out of stack). Even if you would handle this exception what would you like to do? You are out of stack so your options are very limited (for example even defining a local variable, or calling a function will probably cause another exception).

This is why program shouldn't handle such exceptions - at the application level, you just don't have enough wisdom to properly recover, while OS is able to clean up the mess your app produced.

That being said, Windows allows you to catch such exceptions... Structured Exception Handling can be used to catch both hardware and software exceptions on Windows. But, if you're wise programmer, you probably won't do this.

Structured Exception Handling

More on hardware exceptions

---

Related Topics