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

Question

How do I compile a self-referencing function to perform iterative tasks?

The naive approach doesn't seem to work. Here is a simple example to illustrate the problem:

SetSystemOptions["CompileOptions" -> "CompileReportExternal" -> True];

f = Compile[{{r, _Integer}, {x, _Complex}},
      Which[
        r == 0,  x,
        True,    x*f[r - 1, x/2]
      ]
     , {{f[__], _Complex}}, 
       CompilationOptions -> {"InlineExternalDefinitions" -> True}
     ]

Compile::extscalar : $f\big[r-1,\frac{x}{2}\big]$ cannot be compiled and will by evaluated externally. The result is assumed to be type Complex. >>

Answer 1

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@
*)

Answer 2

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.