You do not need recursion, and as you suggest, and as confirmed by
Dave Clarke's answer, you only need conditionals, loops and memory
allocation and assignment.
You can use it to simulate recursion. Or more simply you can use it to
implement arbitrary Turing machines. Just do it for a universal TM, so
you get to implement only one :)
You can actually almost also do it without loops, but not quite. You
need at least one loop if you expect to have infinite computations,
which is implied by Turing power.
However, it could be an implicit loop that loops back to the beginning
of the program, unless you execute a termination statement.
You can remark that control of a Turing Machine has exactly that: a
single loop applied to a case statement, looking up a transition
If you wonder how abitrary many loops can be encoded into a single loop, is
is very similar to dovetailing techniques use to explore space
according to several indices. Think of indexing all pairs of
natural numbers, with or without upperbounds, with a single integer.
Added after the question was modified:
If you consider "every problem, that we can solve using recursions",
rather than "any problem", you do not change the question, unless you
are a lot more precise (and restrictive) about what else is available,
and what use of recursion you allow.
But an unrestricted recursion will give you at least one unlimited
loop, which is usually enough to get Turing Power, if you allow
unlimited memory allocation.
Note that there are limited uses of recursion that keep you below
Turing Power, in precise settings. Look for example at primitive
I understand from your later comment that you made that change, so as to limit the request for solvability to what was already solvable, thus excluding such problems as the halting problem. If that is the intent, it is of course better stated. But, I guess, everyone had instinctively understood it that way, and the change was disconcerting (at least for me).