algorithm - 有效地评估递归函数？

Question

我在之前的采访中遇到了一个有趣的谜题。您需要实现一个符合以下条件的函数：

m, n - positive integer numbers > 0
F(m, n) = F(m-1, n-1) + F(m, n-1)
F(1, n) = 1
F(m, 1) = 1

显然你可以编写递归实现：

int F(int m, int n)
{
    if(m == 1) return 1;
    if(n == 1) return 1;
    return F(m-1, n-1) + F(m, n-1);
}

但是对于等于十亿的输入数据，它将运行很长时间，因为它将获得 2^1000000000 次迭代 :) 有人知道如何优化这个解决方案吗？

Answer 1

function F(m, n)
    v = 1
    s = 1
    k = 1
    while k < m do
        v = v * (n-k) / k
        s = s + v
        k = k + 1
    end
    return s
end