stackoverflow by a recursion

Question

Possible Duplicate:
Runtime exception, recursion too deep

I'm getting a problem while developing a c#.net program and I've simplified it to a simple problem, I need to understand why does this code throw a stackoverflow exception if I call the function like this :

CheckFunc(16000);

but works fine if I call it like this

CheckFunc(1000);

here is the function :

private void CheckFunc(Int32 i)
{
    if (i == 0)
        MessageBox.Show("good");
    else
        CheckFunc(i - 1);
}

tried to make the code as simple as it can get...

I understand that there is a stack that gets overflowed but which stack ? How can I fix this ?

Thanks.

Look at : http://stackoverflow.com/questions/4106708/runtime-exception-recursion-too-deep — Tisho, Jul 03 '12 at 13:11

score 12 · Accepted Answer · answered Jul 03 '12 at 13:12

The problem is indeed stack overflow.

Why it happens:

The stack is a special memory region, where there are a few things stored:

local variables for functions
function parameters
(most importantly) function return addresses. When you return from a function, this is how the processor knows where to get back.

The problem is that this memory region is limited. Recursive calls will add a significant amount of data on this stack, quickly filling it.

How to fix it:

There are several ways:

reduce the number of variables, if you have a local array in a recursive function, you are looking for trouble.
reduce the number of parameters for the function (apparently not the case here)
reduce the number of recursive calls.

If this is not enough, the only solution is to find an iterative solution.

score 11 · Answer 2 · answered Jul 03 '12 at 13:10

11

It's because you simply don't have enough stack space to recurse 16000 times.

Recursion should almost invariably be to a MUCH lower level than that! Otherwise, rewrite as a loop. You CANNOT fix this any other way.

answered Jul 03 '12 at 13:10

Matthew Watson

104,400
10
158
276

score 2 · Answer 3 · answered Jul 03 '12 at 13:19

You need to read about the stack, and how it is used in program execution. In a nutshell, your function fails because it recursively calls itself too many times. The stack, like the heap, has a finite size, but unlike the heap, it is generally much smaller. Every time your function calls itself, some memory in the stack is used to hold information about the function call and variables local to the function (a reference to the variable i in your example). This is called a stack frame. When too many stack frames are created because the recursion is too deep, there is a stack overflow.

You should remove the recursion in CheckFunc, and call it from a loop instead.

Tigran · Answer 4 · 2012-07-03T13:13:01.367

0

There is a limit of Call Stack in C#. And in the first case you exceeed that number, so you get Stack Overflow Exception.

There is no way to fix this, but you naturally can escape of it, by reducing your recursion deepness.

edited Jul 03 '12 at 13:13

answered Jul 03 '12 at 13:10

Tigran

61,654
8
86
123

score 0 · Answer 5 · answered Jul 03 '12 at 13:12

0

I would prefer to do it iterativ. If u have 16000 recursion-steps it will be very slow (i think).

answered Jul 03 '12 at 13:12

Tomtom

9,087
7
52
95

score 0 · Answer 6 · answered Jul 03 '12 at 13:19

The call stack overflows.

Whenever you call a function (or whatever the programming language calls it, "subroutine", "method", whatever), the CPU stores the address of the location where it has to return to after the function finishes. In addition, "local" variables or parameters are usually stored on the stack too.

That stack has a fixed size, which can usually be increased with some magic -- when you create a thread you can usually supply a stacksize, and when you link a program there might also be a linker option to set a stack size.

Basically, you code creates 16000 copies of "i" on the stack, as well as 16000 return pointers, plus anything the compiler might store on the stack on function calls. In your other attempt you only made 1000 copies of these things.

Of course, you're doing something called "tail recursion" which should get optimized away; don't ask me why your compiler doesn't do that.

score 0 · Answer 7 · answered Jul 03 '12 at 13:31

That's basically because your use of recursion is wrong.

The stack that is overflown is the call stack of the process. The stack is used for the parameters that is sent to a method, and the return address for the call, and also for local variables in the method.

For each call, this is added to the stack:

+---------------------+
|                     |
         ...
|                     |
+---------------------+  <-- stack pointer before call
| parameter: int      |
+---------------------+
| return address      |
+---------------------+
| stack frame for     |
|   local variables   |
+---------------------+  <-- stack pointer in the call

Each recursive call will add another chunk to the stack, and as the stack space is limited (to 2 MB IIRC), you will fill up the stack if you do recursion that goes seveal thousand levels deep.

When using recursion in a good way, you rather try to split the data to process in half, not shave off a single piece. Basically:

private void CheckFunc(int i) {
  if (i == 0) {
    MessageBox.Show("good");
  } else {
    CheckFunc(i / 2);
  }
}

This recursion would never go deeper than 31 levels for any integer value.

stackoverflow by a recursion

7 Answers7

Why it happens:

How to fix it: