ビンゴとしての反復関数への再帰関数

Question

私はアルゴリズムが新しく、この表示関数がどのように再帰から反復に変換/変換されるのだろうと思っています。変換する際に何を覚えておく必要がありますか？

public int binom(int n, int k) 
{ 
    if (k == 0 || n == k) { return 1; } 

    return binom(n - 1, k - 1) + binom(n - 1, k); 
} 

ありがとうございます！

Answer 1

あなただけの再帰的なコードを見て、それを解読しようとすると、この問題は、それほど簡単ではありません。 しかし、それは（N K以上）、すなわち、二項係数は

n!/(k! * (n - k)!) 

のように書くことができることを、あなたのために役立つヒントかもしれません「！」階乗を示す。 ループの階乗（すなわち反復）を計算するのは簡単です。

中間結果が大きすぎる場合、計算前に短縮することができます。あなたはどちらかの用語を短くすることができます！または項（n-k）！ （あなたはより大きなものを選ぶだろう）。たとえば、n = 5およびk = 3の場合、 （1 * 2 * 3 * 4 * 5）/（（1 * 2 * 3）*（1 * 2））=（4 * 5）/ * 2）

スポイラー-アラーム：

public static int binomial(int n, int k) { 
    int nMinusK = n - k; 
    if (n < nMinusK) { 
     //Switch n and nMinusK 
     int temp = n; 
     n = nMinusK; 
     nMinusK = temp; 
    } 

    int result = 1; 

    // n!/k! 
    for (int i = k + 1; i <= n; i++) { 
     result *= i; 
    } 

    //Division by (n-k)! 
    for (int j = 1; j <= nMinusK; j++) { 
     result = result/j; 
    } 
    return result; 
} 

Answer 2

2進係数の乗法形式を使用できます（例：Wikia）。これは教員やループで簡単に実装できます。実際に