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

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. >>

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}},
answer = 1 + 0 I;
rCurr = r;
xCurr = x;
While[rCurr > 0,
rCurr--;
xCurr /= 2;
];
],
];


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


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.

• "InlineCompiledFunctions" -> False` isn't necessary actually :) – xzczd Oct 7 '15 at 4:04
• This is very a helpful workaround. It is unfortunate that recursively defined functions cannot be compiled to WVM – QuantumDot Oct 9 '15 at 21:59
• To Marius answer: this will not really do the job. The point is that the compiled function you create in the second run of the compilation will actually refer to the one compiled in the first run. The later in turn will invoke MainEvaluate. You can indeed model something like compiled recursion this way if there is predefined (and) small maximal recursion depth that you need. For recursion depth r you need to compile r times to avoid MainEvaluate at runtime. The final executable code quickly becomes heavy though. – Ivan Protopopov Dec 19 '17 at 11:04