You can compile away those issues with a sufficiently smart compiler!

https://dl.acm.org/citation.cfm?id=2364563

(Caveat: I'm the author of that paper)

You can do tail recursion without a stack...but still, you'd have to branch, which GPUs hate doing.

NVIDIA hardware with compute capability 2.0 and support for CUDA 3.1 (e.g. Fermi chips) have recursion.