Here's a patch which eliminates recursion in all the fns mentioned in the ticket name.
I haven't done much in the way of measuring the impact on perf; a naive benchmark of (assoc huge-vector 123 :foo) seems to indicate a modest perf gain (a few percent shaved off the runtime).
Note that whether pop-tail as implemented in this patch is an improvement over the previous version is not that clear, since it needs to precalculate the level at which the main loop should terminate. Careful measurements will be necessary. (I wouldn't be surprised if the difference turned out to be unmeasurable, in which case I guess we needn't bother with the change.)
push-tail and do-assoc have no such problems – all the work being done needs to be done (and is now done in a non-recursive fashion).
Hm... Actually that probably means this patch should be split in two (pop-tail & rest). I'll get around to that soon.
More importantly, some benchmarks for large data structures should be added (assoc / conj of 32 items (at any rate, a large enough number of items for the tail to be pushed in) / repeated pops (again, enough to pop the tail)). ("Large" here means "large enough for the shift of the vector to grow at least to 10", meaning size > 1024 + 32; shift 15 would be better, requiring size > 32768 + 32.)