After taking a step back from the given definition, it seems to me that the `Mod[...,2]' aren't quite capturing the real periodicity interval of the four case distinctions that are required here.
A more natural approach would be to use Mod[...,4] and make the case distinction based on the four possible values of the remainder.
If $m$ is an integer, the four cases are that the argument is equal to $2(2m)$ (even), $2(2m)+1$ (odd), $2(2m+1)$ (even) or $2(2m+1)+1$ (odd). The remainders of these under division by $4$ are $0$, $1$, $2$ and $3$. And here, $2m$ is even while $(2m+1)$ is odd. Then you can write down the cases in a (to me) more readable way:
Clear[f, m, rule]
rule = {
{m_, 0} :> f[2 m],
{m_, 1} :> 2 f[2 m] + 1,
{m_, 2} :> 2 f[2 m + 1],
{m_, 3} :> f[2 m + 1]
};
f[0] = 0;
f[x_] := QuotientRemainder[x, 4] /. rule
The recursion is now both readable and fast, even without memoization. With recursion relations, readability is more important to me than terseness.
A little more explanation (so that the answer looks less terse...): I implemented the "If statement" in the form of (delayed) rules that depend on the output of the function QuotientRemainder[x, 4]. That output is a list whose first argument is the integer $m$ I introduced earlier, and the second argument is the remainder on which the case distinction is based.
Therefore, the left-hand sides of the rules (e.g., {m_, 0} :> f[2 m]) are tuples, where now m_ appears instead of m because it is a placeholder for the actual value Quotient[x, 4] when f[x] is called. On the right-hand side of the rules, 2 m or 2 m +1 appears in place of the even or odd integer n in the original formulation.
P.S.
One could also implement conditions using the Switch statement, as in
Clear[h];
h[0] = 0;
h[x_] := Switch[#2,
0, h[2 #1],
1, 2 h[2 #1] + 1,
2, 2 h[2 #1 + 1],
3, h[2 #1 + 1]
] & @@
QuotientRemainder[x, 4]
This follows the same idea as in my first approach, but it doesn't rely on rules. Which of these is clearer may be a matter of taste.
