DaftWullie's comments aren't special to 'efficiently computable' functions $f(x)$ — any function at all which we know how to compute by conventional means, we can compute reversibly with at most a (small!) constant factor overhead.
How to reversibly compute a function
The proof is simple. For any procedure to compute something conventionally — classically and without regard to reversibility — we can suppose that it is described in terms of a circuit consisting of FANOUT, NOT, XOR, and AND gates. (If you prefer a different set of universal logic gates, a very slightly different proof can easily be found for that gate set — but it is important that we explicitly account for when we make copies of a bit, which is what we use FANOUT for.) Then we can stimulate each of the gates FANOUT, XOR, and AND using CNOT and TOFFOLI gates as follows:
$$\begin {aligned}
\mathrm{FANOUT} (a)& = \mathrm{CNOT} (a, 0) \\
\bigl(a, \mathrm{XOR} (a, b) \bigr) & = \mathrm{CNOT} (a, b) \\
\bigl(a, b, \mathrm{AND} (a, b) \bigr) & = \mathrm{TOFFOLI} (a, b, 0)
\end {aligned} $$
Thus it takes exactly one of either CNOT or TOFFOLI (and possibly a fresh bit with the value 0) to simulate the computation of a single FANOUT, XOR, or AND gate.
Composing these in the appropriate way, we can compute any classical function that we know how to compute, using only reversible gates.
If (as is usually the case for quantum computation) the TOFFOLI or CNOT operations are not primitive operations of your computational model, the more important thing is that it be possible to realise those operations somehow. If you can decompose them into a fixed size sequence of primitive operations, then doing the computation reversibly only requires an overhead up to some constant factor, i.e. the size of the most complicated decomposition of those reversible gates. For quantum circuits, it is reasonable to suppose that this factor is at most 15 (which is not wonderful, but from a theoretical standpoint is also not terrible, and can be improved depending on what operations you allow).
This reversible realisation of the computation may require some extra workspace: a number of bits which is at most the number of logic gates in your procedure. In some cases, there may be cleverer ways to reversibly realise the computation which requires fewer additional bits than this: coming up with the most sparing such reversible realisation is not necessarily easy.
On efficient functions
The above remarks apply in principle to any classical circuit construction, and indeed to the primitive operations in any higher-level gate model (e.g. the CORDIC-based circuits of your question or any digit-extraction algorithm to compute some function). In principle, given a modest amount of (sufficiently high quality) additional memory, we can simulate any such circuit on a gate-by-gate basis to provide reversible equivalents with the same number of gates, or nearly so.
For more complicated functions, there is ironically enough more opportunities to save on the additional workspace required, which are impossible for the simpler gates (because those gates are too simple to provide opportunities to save) — economies of scale become possible, though not guaranteed.
The important part is that, additional workspace aside, these realisations will respect most notions of 'efficiency'. It does not increase the depth or size of the circuit by more than a constant factor, if at all. If you care about polynomial-size, linear-size, poly-log-depth, what-have-you — this simulation method preserves it.
