Recursive function to compiled version

Question

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

Answer 1

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