mathematica에서 재귀 관계를 효율적으로 계산하는 방법은 무엇입니까?

Question

해결할 재귀가 있습니다.

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 

그러나 다음의 MMA 코드는 [40,20] f를 계산할 참을 오래 걸리는

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]];] 

매우 비효율적이다. 누구든지이 일을하는 효율적인 방법을 제안 해 주시겠습니까? 많은 감사합니다!

Answer 1

표준 트릭은 중간 값을 저장하는 것입니다. 다음은 0.000025 초가 걸린다.

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]]