# Optimize recurrence output

I have recurrence and I need to calculate first $N$ members of the sequence

ClearAll[aa];
l=3;
aa[n_, l_] := If[n <= l,
Quotient[n, l],
(l + 2 (n - l) aa[n - l, l] + (n - l) (n - 1) aa[n - 1, l])/(n*(n + 1 - l))
]

Table[aa[i, l], {i, 0, 30}] // AbsoluteTiming


I guess it is stupid to use Table since its recalculate some of the members several times. How I can output all members in one pass? Can I use RecurrenceTable in this case and is it the quickest way to do it?

-

Use memoization:

ClearAll[aa, bb];
l = 3;
n = 30;
aa[n_, l_] := If[n <= l, Quotient[n, l], (l + 2 (n - l) aa[n - l, l] + (n - l) (n - 1) aa[n - 1, l])/(n*(n +  1 - l))]
bb[n_, l_] := bb[n, l] = If[n <= l, Quotient[n, l], (l + 2 (n - l) bb[n - l, l] + (n - l) (n - 1) bb[n - 1, l])/(n*(n + 1 - l))]

Table[aa[i, l], {i, 0, n}] // AbsoluteTiming // First
Table[bb[i, l], {i, 0, n}] // AbsoluteTiming // First

(*
2.8
0.
*)

-

As you suspect,RecurrenceTableis fast. I modified your functionaato eliminate the variablel, and renamed this variable tosto avoid confusion with the digit 1. This is not perfect code, since I have to assume the casesa[n=0]=0, anda[j]=1for allj>0whens=1.

s = 3;
RecurrenceTable[
{
aa[n]==(s+2(n-s) aa[n-s] + (n-s) (n-1) aa[n-1])/(n*(n+1-s)),