How to compile self-referencing functions (to perform recursive a task)

I haven't found a way to compile recursive functions to WVM, but you can do it if you compile to C: the trick is to use

CompilationOptions -> {"InlineExternalDefinitions" -> True, 
"InlineCompiledFunctions" -> False}

along with

CompilationTarget -> "C"

If you then evaluate the following code twice, you will see that f calls a LibraryFunction, which tells you that it has been compiled:

f = Compile[{{r, _Integer}, {x, _Complex}},
  If[
    r == 0,
    x,
    x*f[r - 1, x/2]
  ], 
   CompilationOptions -> {"InlineExternalDefinitions" -> True,
                         "InlineCompiledFunctions" -> False},
   CompilationTarget -> "C"
 ]

The part specifying the return value of f is not needed as MMA figures it out, and I changed the Which to an If since you only test one thing.

Leonid Shifrin's answer here may be useful (not just for your current problem, but for many, many compilation questions) as it gives advice for what can and what cannot be compiled. Recursion is explicitly called out as not a candidate. However procedural functions are identified as candidates.

So, yeah, if you completely change the intention (from recursion to iteration), no problem...

f[0, x_] := x;
f[r_Integer /; r > 0, x_] := fc[r, x];
fc = Compile[{{r, _Integer}, {x, _Complex}},
    Module[{answer, rCurr, xCurr},
        answer = 1 + 0 I;
        rCurr = r;
        xCurr = x;
        While[rCurr > 0, 
            answer *= xCurr;
            rCurr--;
            xCurr /= 2;
        ];
        answer
    ], 
    {{answer, _Complex}}
];

Then

<< CompiledFunctionTools`
CompilePrint[fc]
(*
    2 arguments
    1 Boolean register
    7 Integer registers
    2 Real registers
    6 Complex registers
    Underflow checking off
    Overflow checking off
    Integer overflow checking on
    RuntimeAttributes -> {}

    I0 = A1
    C0 = A2
    I2 = 0
    C1 = 0. + 1. I
    I6 = 2
    I1 = 1
    R1 = 0.
    Result = C4

1   R0 = I2
2   C2 = R0 + R1 I
3   C2 = C2 * C1
4   R0 = I1
5   C4 = R0 + R1 I
6   C4 = C4 + C2
7   I3 = I0
8   C2 = C0
9   B0 = I2 < I3
10  if[ !B0] goto 19
11  C5 = C4 * C2
12  C4 = C5
13  I4 = I3
14  I5 = Subtract[ I4, I1]
15  I3 = I5
16  C5 = Divide[ C2, I6]
17  C2 = C5
18  goto 9
19  Return@
*)