# Recursive function to compiled version

I have looked up some articles about the compiling recursive functions. I know usually there is no general solution to these kinds of questions. And my case is a little bit different (or more complicated) so I decide to simplify it and ask here:

The original recursive function in my case has been simplified as below:

Clear[f]
x = 0.1; f[0] = 1.; f[1] = 2.;
f[n_] := f[n] = 20*x*f[n - 1] + n*f[n - 2];


And my desired output result was calculated by:

Table[f[n] 2 n x, {n, 0, 10}]
(* Output: {0., 0.4, 2.4, 10.8, 48., 210., 936., 4242., 19680., 93366., 453480.} *)


To transform it into a compiled version, what I did is that I first wrote a compiled fc function as shown below: (Note: it's not the best way to use Do but that's all I can think of ):

fc = Compile[{{x, _Real}}, Module[{t}, t = {1., 2};
t = Join[t, Table[0., {10}]];
Do[t[[n + 2]] = (20*x*t[[n + 1]] + (n + 1)*t[[n]]), {n, 10}]; Most@t]
]


It works okay for using fc as a compiled replacement by f:

Table[f[n], {n, 0, 10}]
(*{1, 2, 6., 18., 60., 210., 780., 3030., 12300., 51870., 226740.}*)

fc[0.1]
(*{1., 2., 6., 18., 60., 210., 780., 3030., 12300., 51870.,226740.}*)


However, my questions are:

1- I don't know how to take the 2*n*x part into the final computation to get my desired result.

2- fc only works fine when x is one-dimensional value. But my project requires larger data-set to handle with and that's why I am trying to use Compile. So how to adjust it to work on a real number list, for example, when x = {0.1,0.2,0.3...}?

• What do you mean by " I don't know how to take the 2*n*x part into the final computation to get my desired result." What is your desired result? – Henrik Schumacher Nov 29 '18 at 21:59
• My final computation would include 2*n*x, so in the uncompiled version, it was calculated by Table[f[n] 2*n*x, {n, 0, 10}], I do not know how to transform this. – leon365 Nov 29 '18 at 23:22
• Okay. I edited my post. Please have a look. – Henrik Schumacher Nov 30 '18 at 8:07

So how to adjust it to work on a real number list, for example, when x = {0.1,0.2,0.3...}?

If x is a list of reals, then just compile fc with the addictional option RuntimeAttributes-> {Listable} and call fc[x]. Parallelization -> True will also enable parallelization (does only work if RuntimeAttributes-> {Listable} is also set).

fc2 = Compile[{{x, _Real}, {iter, _Integer}},
Module[{t},
t = {1., 2.};
t = Join[t, Table[0., {iter}]];
Do[
t[[n + 2]] = (20. x t[[n + 1]] + (n + 1) t[[n]]),
{n, iter}
];
Most[t] Range[0, iter] (2. x)
],
CompilationTarget -> "C",
RuntimeAttributes -> {Listable},
Parallelization -> True,
RuntimeOptions -> "Speed"
];


A quick test (also with the vectorized version of your old memoization approach):

x = Subdivide[0., 10., 1000000];
ClearAll[f];
f[0] = 1. + 0. x; f[1] = 2. + 0. x;
f[n_] := f[n] = 20. x f[n - 1] + n f[n - 2];
aa = Transpose[Table[f[n] 2 n x, {n, 0, 50}]]; // AbsoluteTiming // First
bb = fc2[x, 50]; // AbsoluteTiming // First
aa == bb


1.59957

0.352834

True