Recursive function causing an overflow despite it's not infinite

Question

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.

• asawyer: 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.
• devshorts: 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
• Micah Armantrout: Maybe you should try to describe what your wanting to accomplish this looks really unnecessarily overly complex
• Joshua Van Hoesen: @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.

Answer 1

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.

Answer 2

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: When downvoting pleaes leave a comment. Thanks.

Answer 3

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

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

Answer 4

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.

• Nathan Abramov: I tried to use the optimization but i couldn't understand what to do, when I check the optimize property it wont do anything.
• devshorts: @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
• Samuel Neff: 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.