# Use Nest in a recurrence function

I have following recurrence function:

al0[k_, ee_] := (k d[k, ee] + (k + 1) d[k + 1, ee]) (-1)^k ;
al1[k_, ee_] :=
al0[k, ee] - (k + 1)/(2 k + 3) al0[k + 1, ee] - k/(2 k - 1) al0[k - 1, ee];
al2[k_, ee_] :=
al1[k, ee] - (k + 1)/(2 k + 3) al1[k + 1, ee] - k/(2 k - 1) al1[k - 1, ee];
al3[k_, ee_] :=
al2[k, ee] - (k + 1)/(2 k + 3) al2[k + 1, ee] - k/(2 k - 1) al2[k - 1, ee];


Could I use Nest to make it simpler and faster? If not nest, anything else i can use?

## 2 Answers

you can use memoization, which use more memory but gives you a faster answer

   al[0, k_, ee_] :=
al[0, k, ee] = (k d[k, ee] + (k + 1) d[k + 1, ee]) (-1)^k;

al[i_, k_, ee_] :=
al[i, k, ee] =
al[i - 1, k, ee] - (k + 1)/(2 k + 3) al[i - 1, k + 1, ee] -
k/(2 k - 1) al[i - 1, k - 1, ee];

al3[k, ee] == al[3, k, ee]


True

i added a third index to control the number of iterations

• @Edmund it should work now – Alucard Sep 27 '17 at 4:51
• I find that this behaves much better than alNest as it allows e.g. al[22, .3, .7], assuming a numeric definition for d e.g. d = Plus. alNest will choke attempting to making one huge Symbolic expression. ( @Edmund ) – Mr.Wizard Sep 27 '17 at 7:06
• @Mr.Wizard Yes. It the symbolic expression does get complicated for small n.(+1) – Edmund Sep 27 '17 at 10:23
• @Mr.Wizard Humm, on second thought would not al and alNest have equal performance on the first run since al is traversing the memoization from highest to lowest and needs the lower indices. Also, with alNest the result is a function in which k and ee are parameters. Therefore, for any particular nesting alNest will be faster on the following runs since the function does not have to be rebuilt for new values of k and ee at that nesting level. – Edmund Sep 27 '17 at 10:44
• @Edmund Did you try to evaluate alNest[22]? I think you'll find it's well beyond the capacity of the system. On the other hand al[22, .3, .7] works just fine if we define d = Plus or some other numeric operator. – Mr.Wizard Sep 27 '17 at 12:08

You may use Nest by returning a Function for each nested level.

With al0as defined in OP

alNest[n_Integer?Positive] :=
Nest[
Function[{foo},
Function[{k, ee},
foo[k, ee] - (k + 1)/(2 k + 3) foo[k + 1, ee] - k/(2 k - 1) foo[k - 1, ee]
]],
al0,
n]


Then

opSol3 = al3[k, ee] // FullSimplify;
nestSol3 = alNest[3][k, ee] // FullSimplify;
opSol3 == nestSol3

True


alNest returns the nested function. This can be saved to a variable for reuse (nest3 = alNest[3];) and used multiple times later on (nest3[k, ee]), or it can be used immediately as in the code snippet above.

Hope this helps.