Matlab 递归：低效代码还是复杂递归？

Question

我正在努力在合理的执行时间内解决这个递归问题。

在这里，我展示了基本上计算多项式系数的递归函数。

function [ coeff ] = get_coeff( n, k, tau, x )

if(n == 0) % 1st exit condition
    coeff = 0;
else
    if(k == 0) % 2nd exit condition
        coeff = max(0, n*tau-x)^n;
    else % Else recursion
        total = 0;
        for l = k-1:n-2
            total = total + nchoosek(l, k-1)*tau^(l-k+1)*get_coeff(n-1, l, tau, x);
        end
        coeff = (n/k) * total;            
    end
end

end

 % This symbolic summation solution gives numerical errors, probably due to rounding
 % effects.
 %           syms l;
 %           f = nchoosek(l, k-1)*tau^(l-k+1)*get_coeff(n-1, l, tau, x);
 %           coeff = (n/k) * symsum(f, l, k-1, n-2);

这是我使用递归函数的主要脚本：

Tau = 1;
ns = [3];
%delays = 0:0.25:8;
delays = [0];
F_x = zeros(1, size(delays, 2));
rho = 0.95;
tic
for ns_index = 1: size(ns, 2)

  T = Tau*(ns(ns_index)+1)/rho;

  % Iterate delays (x)
  for delay_index = 1:size(delays, 2)
     total = 0;

     % Iterate polynomial.
     for l = 0:ns(ns_index)-1
        total = total + get_coeff(ns(ns_index), l, Tau, delays(delay_index))*(T - ns(ns_index)*Tau + delays(delay_index))^l;
     end

    F_x(1, delay_index) = T^(-ns(ns_index))*total;

  end

end
toc

我已将 "ns" 和 "delays" 向量简化为包含单个值，以便更容易理解。总之，对于 "ns" 的固定值，我需要使用递归函数计算多项式的所有系数，并在 "delays" 处计算其最终值。通过增加 "delays" 中的点数，我可以看到固定 "ns" 的曲线。我的问题是：对于 1 到 10 之间的任何 "ns"，计算速度非常快，大约为 0.069356 秒（即使对于整个 "delays" 向量）。相反，对于 ns = [15] 或 [20]，计算时间会增加很多（我什至没能看到结果）。我不热衷于评估计算复杂性，所以我不知道我的代码中是否存在问题（可能是 nchoosek 函数？或 for 循环？）或者这可能是它必须考虑的递归方式问题。

编辑：正如阿德里安所说，我看到这确实是计算量的阶乘增长。您认为 nchoosek 的任何一种近似值都有助于解决这个问题吗？类似于：en.wikipedia.org/wiki/Stirling%27s_approximation

The last formula in this paper 是我要实现的（注意我为 tau 更改了 delta）：

Answer 1

我已经运行你的代码中的配置文件，我得到了这个：

我看起来大部分时间都花在了 nchoosek 上，nchoosek 接受两个整数作为输入。您可以尝试预先计算所需的值并将它们存储在矩阵中以便更快地访问！

编辑：我尝试这样预先计算 nchoosek：

for i = 0 : ns
    for j = 0 : ns
        if j < i
            nchoosek_(i+1,j+1) = nchoosek(i,j);
        else
            nchoosek_(i+1,j+1) = NaN;
        end
    end
end

然后在函数内：

total = total + nchoosek_(l+1, k-1+1)*tau^(l-k+1)*get_coeff(n-1, l, tau, x , nchoosek_);

它似乎有效，我在 ns = 12 时得到了很好的改进：

但我还是撞墙了 ns = 15...

Answer 2

所以我终于设法在合理的时间内计算出系数。基本上，我采纳了 Adriaan 和 rahnema1 的建议并创建了一个 ns 乘 ns 矩阵来存储我以递归方式计算的所有系数。因此，当重复递归树的某个叶子时，我可以通过从矩阵中提取值来修剪树。请注意，增益不是基于预先计算的值（因为我在旅途中计算它们），而是基于修剪递归次数。这里有一些数字：

ns = 10; delay = 0: 调用旧递归函数的次数是 23713。现在，这在 175 次调用中解决了。
对于 ns = 10; delay = [0:0.25:8]：782529 次调用旧函数和 2.74 秒的执行时间，495 次调用新函数和 0.02 次，快了 125 倍。

Matlab 递归：低效代码还是复杂递归？

Matlab recursion: inefficient code or complex recursion?

recursion

time

matlab

execution

coding-efficiency