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);
}

しかし、入力データが10億に等しい場合、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