Brainfuck is a classical example of a turing complete language that doesn't have a notion of functions. What does "recursion" mean here? Nothing, I think. So you don't need recursion for Turing completeness.
Some people work on languages that support functions as first class objects, which don't natively support recursion. This is nice from a language design standpoint, because functions only see the scope of their arguments and can't look any further. The "Y Combinator" pattern is used to bootstrap recursion into these languages. You may have heard of it.
Turing-incomplete languages can also support unlimited recursion. For example, take a Turing complete language, and equip it with a state of the art theorem prover. Before entering a loop, or calling a function, the theorem prover is allowed to spend up to 1 minute proving that the loop or function call will terminate. If the theorem prover times out, the program halts with an error. Some functions, such as a naive implementation of factorial, can be easily proved to halt for all inputs. So this language allows recursion, but by construction, all programs terminate, so it's turing incomplete.
Obviously using a recursive descent parser is out but thats probably easy to work around right?
I could be wrong tho so don't base mission critical code on this without rigorous testing!
Key to being a good programmer: at least read a bit about the language before speculating about it. Not sure what you mean by "allows constants", but you're only given increment and decrement operators, and a promise that fresh tape is zeroed out.
Brainfuck supports iteration. Performing recursion in a higher level language will still look like iteration in Brainfuck.
