The real problem is that recursion-by-Deferred doesn't have the optimisation for tail recursion found in most functional languages, because that would be very difficult and it's not how Deferreds are usually used.
Actually it *is* supposed to have this sort of optimization. You can see the work on this on my favorite (now long-since closed) Twisted ticket: <http://twistedmatrix.com/trac/ticket/411>.
So it might be interesting to investigate why that doesn't help in this case, and if it could be made to.