Which structures can constitute the foundations of mathematics?

It is a well known view that mathematical logic together with set theory can be used as a foundation for the whole the rest of mathematics. Category theory also has been mentioned as a candidate for this, as an alternative of set theory.

But recently I heard (from a non-mathematician) a view that whole of mathematics could be based on recursive functions instead. Recursive functions as in theory of computations (aka. computable functions).

I have an intuitive notion that recursive functions cannot be used in such way, but I cannot think of the exact reasons why. It seems that using them for foundations would purge out of mathematics computably not representable structures, such as real numbers (leaving only algebraic numbers and some more like e and pi ), but I do not want use this as a counterargument, because of the obvious counter-counter argument: that "true" mathematics is only what is computable and the rest "is made up by man".

Are set theory elements used in an implicit way in theory of recursive functions? If they are, cannot the theory be rephrased in such a way that they are not being used? Take in account that functions like s(x) (i.e. the successor function) would be primitive element of such theory. What about lambda calculus, Turning machine algorithms and other formalizations equivalent to recursive functions?

This whole discussion is related to the Max Tegmark's paper The mathematical universe.