Defining things in a non-recursive manner

In this question I asked, if it was possible to define certain functions without the use of the recursion theorem. The answer, among other things, indicated that it theoretically would be possible, but very tedious. To help me get a feeling of how difficult/tedious things will get, if I don't have the recursion theorem at hand, I was pointed to an exercise in the book Gödel,Escher,Bach by Hofstaedter, which, as the answerer indicates, says

characterize the predicate '$n$ is a power of $2$' in explicit fashion - note that 'explicit' here means without the use of recursion or iteration (which is, for these purposes, recursion in disguise)

Now I wasn't able to find said exercise in the book and I also couldn't solve it, which is why I'm kindly asking for a solution here.

If the above has an explicit solution would it also true that every predicate/function/'mathematical object we get via the recursion theorem' can also be obtained without the recursion theorem, but in a very tedious and "writing-intensive" way ?

-