Instantiation of recursive generic types slows down exponentially the deeper they are nested. Why?

Note: I may have chosen the wrong word in the title; perhaps I'm really talking about polynomial growth here. See the benchmark result at the end of this question.

Let's start with these three recursive generic interfaces^† that represent immutable stacks:

interface IStack<T>
{
    INonEmptyStack<T, IStack<T>> Push(T x);
}

interface IEmptyStack<T> : IStack<T>
{
    new INonEmptyStack<T, IEmptyStack<T>> Push(T x);
}

interface INonEmptyStack<T, out TStackBeneath> : IStack<T>
    where TStackBeneath : IStack<T>
{
    T Top { get; }
    TStackBeneath Pop();
    new INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x);
}

I've created straightforward implementations EmptyStack<T>, NonEmptyStack<T,TStackBeneath>.

Update #1: See the code below.

I've noticed the following things about their runtime performance:

• Pushing 1,000 items onto an EmptyStack<int> for the first time takes more than 7 seconds.
• Pushing 1,000 items onto an EmptyStack<int> takes virtually no time at all afterwards.
• Performance gets exponentially worse the more items I push onto the stack.

Update #2:

• I've finally performed a more precise measurement. See the benchmark code and results below.

• I've only discovered during these tests that .NET 3.5 doesn't seem to allow generic types with a recursion depth ≥ 100. .NET 4 doesn't seem to have this restriction.

The first two facts make me suspect that the slow performance is not