Interview Question: What is Stack Overflow?

Q: What is Stack Overflow?
A: It is a website many people seeking answers from. It is created by the guy writes blogs on Joel on software...

Q: Hang on, I am not asking the website StackOverflow.com and I am not interested in who the hell created it. I am asking Stack, space, Overflow.
A: Ah I see, the Stack Overflow. What is Stack Overflow? It is, stack, hmmm, overflows. In another way, the stack blows out.

Q: Why would it blow out, I mean, overflow?
A: It overflows simply because too much stuff put into the stack while more things are being put in it. Think about last time you blew out a balloon.

Q: Can't remember I ever did that ... anyway, how could it happen, say, in .Net?
A: In .Net normally it happens when it tries to do a recursion too deeply. By default in .Net application running on Windows the stack size is 1 MB. Because of the nature of recursion the method invokes itself repeatedly and each invoke creates a stack frame and each stack frame contains a set of local variables. When it reaches 1 MB and it tries to add another stack frame it throws StackOverflowException.

Q: How can you prevent it from happening, say, you have a very deep tree and you need to traverse it?
A: Of cause a easy solution is to increase the stack for the thread. From .net 4.0 you can define a stack size larger than 1 MB in the Thread constructor, assuming you have the full trust of the code. But this is a bad solution because normally you wouldn't be able to know how big size you need thereby it is still possible to blow it up. If it is a very large tree then we can use the class Stack, which is allocated in the heap, to push and pop the nodes. Here is an example:

public IEnumerable<Node> Iterate(Node rootNode)
{
    if (rootNode == null) yield break;

    var stack = new Stack<Node>();
    stack.Push(rootNode);

    while (stack.Any())
    {
        var currentNode = stack.Pop();
        yield return currentNode;

        if (currentNode.Left != null) stack.Push(currentNode.Left);
        if (currentNode.Right != null) stack.Push(currentNode.Right);
    }
}

public class Node
{
    public string Name { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

Q: What is tail-call recursion?
A: Tail-call recursion is a special case of recursion, in which the last call returns the value immediately. In this case since every call is just simply returns a value which gets from the call it calls thereby we can optimize it by using the same stack frame rather than creating a new one. Sometimes we call it tail-call optimization. Functional languages support this but not C# or CLR until .net 4.0 CLR in a 64bit Windows, which might be optimized by the jitter.