Complexity and stack space usage are two very different things. CPython does indeed place (very!) conservative limits on stack depth, and it also implements generators. I haven't looked at the generator implementation, but it has a number of limits that make it easy to implement — the main one is that generators don't have their own stacks, so can't yield from inside a function they call, the way e.g. Lua coroutines or (effectively) Icon generators can.
I'm sorry, I made something of a terminological error. When I said 'complexity', I was referring to complexity of implementation, not algorithmic time or space complexity. My intention was to assert that implementing generators and implementing tail-call optimization are both endeavors of roughly the same order of engineering difficulty (as the mechanism used to implement TCO is quite simple) and not to compare the stack space required by each.
I also should clarify that at this point, it's likely not reasonable to expect Guido or the Python community to ever turn around and decide to implement TCO, as the current engineering effort required to add TCO to all active implementations of Python is much larger in comparison to the engineering required to add it at an earlier stage. I regard this as a failure of the langauge design from the start, but having made their decision I don't fault the Python community for sticking to it.
I was responding to your "I do not believe that Python does place conservative requirements on an implementation's stack", in response to bcoates's statement that it does, nothing about complexity. I was just trying to clarify (my interpretation of) what he said.
