How to memoize a recursive function in Matlab?

2 次查看（过去 30 天）

Christine Pepin 2020-5-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/528618-how-to-memoize-a-recursive-function-in-matlab

评论： Christine Pepin 2020-5-21

I implemented a recursive function that computes the number of strings (or tosses) of length n with exactly k heads but no more than x of these occuring consecutively (this is for the biased coin tossing problem). For n>20, the execution time is very slow. I would like to reduce it using memoization, but am not sure how to use it correctly in a recursive function. This is my function and how I memoized it:

function C_coeff = NumStrings(n, k, x)
% Recursive function to compute the number of strings of length n with
% exactly k heads but no more than x of these occuring consecutively.
%
    persistent memoizeNS;
    if isempty(memoizeNS)
        memoizeNS = memoize(@NumStrings);
    end
    vec = zeros(1, x+1);    
    if (k <= x)
        C_coeff = nchoosek(n, k);        
    elseif (k == n && k > x)
        C_coeff = 0;
    elseif (x < k && k < n)
        for j = 0:x
            vec(j+1) = memoizeNS(n-1-j, k-j, x);   
        end
        C_coeff = sum(vec);
    else
        return;
    end
end

The function NumStrings(n,k,x) is called from a script and within a loop where k varies (n and x remain fixed). Therefore, a specific C_coeff may show up multiple times within the recursive function and I don't want to compute the same coefficient every time. Using this memoization technique doesn't change the execution time unfortunately. Any hint as to why? Thanks.