0

The following function I wrote causing the program to crash due to the stack overflow, although the recursion is finite. 

public static void Key(char[] chars, int i, int l, string str) {
    string newStr=null;

    for(int j=0; j<l; j++)
        newStr+=chars[i/(int)Math.Pow(68, j)%68];

    if(newStr==str)
        return;

    Key(chars, ++i, l, newStr);
}

When I call the method with these parameters, all goes fine:

Key(chars, 0, 4, "aaaa");

But when it comes to bigger number of calls, it throws the StackOverflowException. So I assume the problem is that althogh the method is finite the call stack gets filled up before the the methods' job is done. So I have a few questions about that:

  1. Why the functions don't get clear from the stack, they are no longer needed, they don't return any value.

  2. And if so, is there a way i could clear the stack manually? I tried the StackTrace class but it's helpless in this case.

Ken Kin
  • 4,503
  • 3
  • 38
  • 76
Nathan Abramov
  • 115
  • 8
  • 4
    I get the strong impression that you don't understand what the stack is or what it does. Please look into that and your questions should be answered on their own. – asawyer Apr 05 '13 at 18:46
  • 2
    Technically your code is tail recursive, if you build this with c# optimizations on you'll never have a stack overflow, you should just get an infinite loop (if your base case is actually never getting hit). Try turning optimizations on and see if you still get a stack overflow – devshorts Apr 05 '13 at 18:50
  • 1
    Maybe you should try to describe what your wanting to accomplish this looks really unnecessarily overly complex – Micah Armantrout Apr 05 '13 at 18:55
  • @Nathan Abramov My suggestion would be to step through your program with the debugger after placing break points and seeing on what iteration it crashes and the conditions therein. – Joshua Van Hoesen Apr 05 '13 at 19:05

4 Answers4

2

1) The function clears when it has ended execution. Calling Key inside of itself means that every call to it will be on the stack until the last call ends, at which stage they will all end in reverse order.

2) You can't clear the stack and carry on with the call.

Jamie Kelly
  • 309
  • 3
  • 15
1

The stack is still limited. For standard C# applications it is 1 MB. For ASP it is 256 KB. If you need more stack space than that, you'll see the exception.

If you create the thread yourself, you can adjust the stack size using this constructor.

Alternatively, you can rewrite your algorithm so it keeps track of state without using recursion.

Brian Rasmussen
  • 114,645
  • 34
  • 221
  • 317
1

It looks like the exit condition of NewStr == Str will never happen and eventually, you will run out of stack.

Metaphor
  • 6,157
  • 10
  • 54
  • 77
  • Why would't it happen? and it does happen when the number of calls are smaller than the number of calls the stack could handle. – Nathan Abramov Apr 05 '13 at 18:51
  • 2
    @NathanAbramov An algorithm working for a subset of possible inputs is not a proof that it works for all possible input. – Ant P Apr 05 '13 at 18:54
  • I don't see the problem, why would't it work for all possible inputs?(regardless the overflow issue) – Nathan Abramov Apr 05 '13 at 18:57
  • 1
    @NathanAbramov, It looks like you are implementing some (potentially known) algorithm that rely on some properties of natural numbers... but you use `Math.Pow` to compute (chars.Length ^ j) which clearly can produce results you don't expect. Your "I said it is finite" proof is not very convincing so far. – Alexei Levenkov Apr 05 '13 at 19:03
  • @AlexeiLevenkov Why would `Math.Pow` produce unexpected results? `i` will keep increasing by 1 every call, which means all possible choices will be computed. – Nathan Abramov Apr 05 '13 at 19:11
  • @NathanAbramov, What do you expect 68^10 to be? I suspect you want 2113922820157210624 instead of more "double" 2113922820157210000... – Alexei Levenkov Apr 05 '13 at 20:04
  • @AlexeiLevenkov 68^10 would not be necessary so i took that in mind. – Nathan Abramov Apr 06 '13 at 08:07
1

So, regardless of whether your code reaches its base case or not, your code should never get a stack overflow exception in production.

For example, this should give us a stack overflow right?

private static void Main(string[] args)
{
    RecursorKey(0);
}

public static int RecursorKey(int val)
{
    return RecursorKey(val ++);
}

In fact it doesn't, if you use .NET 4 and are not debugging and your binary is compiled as release.

This is because the clr is smart enough to do what is called tail recursion. Tail recursion isn't applicable everywhere, but in your case it is, and I was easily able to reproduce your exact problem. In your case, each time you call the function it pushes another stack frame onto the stack, so you get the overflow, even though the algorithm would theoretically end at some point.

To solve your issue, here is how you can enable optimizations.

However, I should point out that Jon Skeet recommends to not rely on tail call optimizations. Given that Jon's a smart guy, I'd listen to it him. If your code is going to encounter large stack depths, try rewriting it without recursion.

Community
  • 1
  • 1
devshorts
  • 8,572
  • 4
  • 50
  • 73
  • I tried to use the optimization but i couldn't understand what to do, when I check the optimize property it wont do anything. – Nathan Abramov Apr 05 '13 at 19:46
  • 2
    @NathanAbramov, so I think the problem here is that tail call optimization only happens on 64 bit machines, not 32 bit. I found this out while researching your question: http://stackoverflow.com/questions/15864670/generate-tail-call-opcode which led me to http://stackoverflow.com/questions/4043821/performance-differences-between-debug-and-release-builds/4045073#4045073. Hope that helps clarify things – devshorts Apr 07 '13 at 19:10
  • This is a fun fact, but since behavior is different in debug vs production and 32-bit vs 64-bit indicates it's not something you'd want to rely on. – Samuel Neff Aug 23 '13 at 14:48