# Create recursive sequence of functions with memoization

I am trying to create a sequence of functions and have it properly memoize the results. The recursive operation is simply convolution, so it possible there is a better way to do this (obviously, if I could find a closed form expression for the n-th convolution, that would be ideal, but I'm not certain I can do that). Here is my current code

f[x_, c2_] := (
Exp[-c2^2/2 + c2 Sqrt[-Log[2 π] - 2 Log[x]]] +
Exp[-c2^2/2 - c2 Sqrt[-Log[2 π] - 2 Log[x]]]
) / Sqrt[(-Log[2 π] - 2 Log[x])]

LogExpect[x_, shift_] := Piecewise[{{f[Exp[x], shift] Exp[x], x < -1/2 Log[2 π]}}, 0]

LogExpectN[t_, n_] := Module[{xx},
LogExpectN[t, n] = Convolve[LogExpectN[xx, n - 1], LogExpect[xx, 0], xx, t]
]
LogExpectN[t_, 1] = LogExpect[t, 0]


In general this works, as it will properly calculate LogExpectN[t,5] for example, and it will memorize that specific result, but if I ask it for LogExpectN[2 t,5] or LogExpectN[x,5] it has to redo the copmutation completely, instead of just plugging 2t or y into the function it already found and thus there is no speed up from the memoization. Is there a way to get the behavior I want?

Edit: By changing the the recursive definition to use a pattern, I have improved things

LogExpectN[t_, n_] := Module[{xx}, LogExpectN[t_, n] = Convolve[LogExpectN[xx, n - 1], LogExpect[xx, 0], xx, t]]


However, This only works if I evaluate consecutive values of n in order. FOr example, after setting the base case for n=1, I can calculate for n=2 and then n=3, but if I try to calculate n=3 directly, it will give me an expression in terms of the internal variable xx$<numbers>$. I am not really sure what is going on here.

• Related, possibly duplicate: (53) – Mr.Wizard Jul 3 '18 at 12:15

Memoize a worker function.

f[x_] := f[x] = (Print["Memoized ", x]; f[x - 1] + 1);
f[0] = 0;
{f[3], f[3]}
(*the first f[3] prints trice, the second does not print*)


Then, use the worker function to memoize your main function.

SetAttributes[g, HoldFirst]
g[x_] := g[x] = f[x];
{g[2 2], g[2 2 + 1]}
(*g[2 2] prints 4, g[2 2 + 1] prints 5*)


Check that the downvalues of the main function have your required behavior.

DownValues[g]
(*there are entries for 2 2 and 2 2 + 1*)


Note that you cannot combine the worker function and the main function in one step because HoldFirst will not allow to get to the stopping h[0].

SetAttributes[h, HoldFirst];
h[x_] := h[x] = (Print["Memoized ", x]; h[x - 1] + 1);
h[0] = 0;
h[3]
(*Recursion depth of 1024 exceeded*)


UPDATE

Consider

LogExpectN[t, n] = worker[n][t]


Because there are two variables, there are two memoizations involved. One to compute the n-th worker function and another to avoid replacing t in that worker function. The code before this update takes care of second type of memoization. The first memoization is trickier because you are computing a function.

f[x_, c2_] := (Exp[-c2^2/2 + c2 Sqrt[-Log[2 π] - 2 Log[x]]] +
Exp[-c2^2/2 - c2 Sqrt[-Log[2 π] - 2 Log[x]]])/
Sqrt[(-Log[2 π] - 2 Log[x])];

LogExpectN[t_, n_] := LogExpectN[t, n] = (Print["Memoizing t=", t]; worker[n][t]);

worker[n_] :=
worker[n] =
Module[{xx, tt, integral}, Print["Memoizing n=", n];
integral = Convolve[worker[n - 1][xx], stoppper[0][xx], xx, tt];
Function @@ {tt, integral}];

worker[1] = stoppper[0];

stoppper[shift_] :=
Function[{x},
Piecewise[{{f[Exp[x], shift] Exp[x], x < -1/2 Log[2 π]}}, 0]];

LogExpectN[t, 2]
(*Prints t=t and n=2*)

LogExpectN[t, 3]
(*Prints t=t and n=3*)

LogExpectN[3 t, 2]
(*Prints t=3 t only*)

• Thanks. When I manage to apply this to my code I will accept the answer. Still trying to figure out the how and why of this. – irh Jul 3 '18 at 12:44
• After futzing around, I can't get this approach to work. – irh Jul 3 '18 at 14:08
• @irh Maybe, your problem is needing to evaluate the integral before memoizing the worker function. In the update, check the usage of Function @@. – Hector Jul 13 '18 at 16:12