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.

Improve this question
4
  • 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. Commented Apr 5, 2013 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 Commented Apr 5, 2013 at 18:50
  • 1
    Maybe you should try to describe what your wanting to accomplish this looks really unnecessarily overly complex Commented Apr 5, 2013 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. Commented Apr 5, 2013 at 19:05

4 Answers 4

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

1 Comment

When downvoting pleaes leave a comment. Thanks.
1

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

Improve this answer

7 Comments

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.
@NathanAbramov An algorithm working for a subset of possible inputs is not a proof that it works for all possible input.
I don't see the problem, why would't it work for all possible inputs?(regardless the overflow issue)
@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.
@AlexeiLevenkov Why would Math.Pow produce unexpected results? i will keep increasing by 1 every call, which means all possible choices will be computed.
|
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.

Improve this answer

3 Comments

I tried to use the optimization but i couldn't understand what to do, when I check the optimize property it wont do anything.
@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: stackoverflow.com/questions/15864670/generate-tail-call-opcode which led me to stackoverflow.com/questions/4043821/…. Hope that helps clarify things
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.