Of course, if your language doesn't support recursion it probably doesn't have first-class functions either. It's pretty trivial to implement recursion if you can pass a function pointer around.
fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.
C can do recursion. It can't do first class functions, though it can pass function pointers. It just can't create new functions dynamically based on non local variables, at least not without shenanigans.
That's one possible implementation of recursion on commodity hardware. Recursion itself is a mathematical method for defining a function which may not even be computable, or may be computable using other primitives.