Comment calculer les relations de récursion dans Mathematica efficacement?

Question

J'ai récursion à résoudre pour.

f(m,n)=Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]
f(0,n)=1, f(1,n)=n

Cependant, le code suivant mma est très inefficace

f[m_, n_] := Module[{},
  If[m < 0, Return[0];];
  If[m == 0, Return[1];];
  If[m == 1, Return[n];];
  Return[Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]];]

Il faut insupportablement long pour calculer f [40,20]. Quelqu'un pourrait-il s'il vous plaît suggérer un moyen efficace de le faire? Un grand merci!

Answer 1

astuce standard consiste à enregistrer les valeurs intermédiaires. Ce qui suit prend 0,000025 secondes

f[m_, n_] := 0 /; m < 0;
f[0, n_] := 1;
f[1, n_] := n;
f[m_, n_] := (f[m, n] = 
    Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, 
       n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]);
AbsoluteTiming[f[40, 20]]