原题：

1.1 Basic Programming Model
Creative Problems
1.1.27
Estimate the number of recursive calls that would be used by the code to compute binomial(100,50).Develop a better implementation that is based on saving computed values in an array.

public static double binomial(int N, int k, double p){    if (N == 0 && k == 0)        return 1.0;    if (N < 0 || k < 0)        return 0.0;    return (1.0 - p) * binomial(N-1, k, p) + p * binomial(N-1, k-1, p);}

因为对于递归其实了解得还不算太深刻，所以乍一看到这个code还是有点懵（这和我想象中的二项分布不一样啊xxx
然后去谷歌了一下发现正好有人写了分析这道题的blog
链接在此
主要是对于这个和排列组合有关的递推式不是很了解（就是不知道），所以也看不明白这个递归的code

不过原code来算二项分布真的很灾难，N=10的时候调用次数就有2000+了，按原题给的那个100的数据我IDEA直接就3s之内跑不完了

改进方法

  1. 非递归

    • 要算二项分布的话第一反应其实就是直接根据公式来，计算组合数和幂运算
    • 但测试了一下发现，计算组合数需要用到阶乘，N过大算出来的阶乘会overflow，结果为0（用int和long都不可以），所以不能直接算组合数

    • 只要进行一点小小的调整：

      • 组合数写成阶乘的形式时上下是可以约分的，不需要真的算出N的阶乘（如链接中的做法）

  2. 递归

    • 根据题目中给的提示“saving computed values in an array”
    • 原链接中有答案
  3. 网站上给出的题解（递归思想的非递归写法）
/**解释：利用的思想仍旧是(n,k) = p * (n-1,k-1) + (1-p) * (n-1,k)(n,k)指N = n, k = k的情况理解：想象要在n个人里面挑k个人，假设第k个人被选中了(概率为p)，那么就是(n-1,k-1)的情况，假设第k个人没有被选中(概率为1-p)，那么就是(n-1,k)的情况*/public static double binomial2(int N, int k, double p) {    double[][] b = new double[N+1][k+1];    // base cases    // 当k为0时，都为(1-p)^i    for (int i = 0; i <= N; i++)        b[i][0] = Math.pow(1.0 - p, i);    b[0][0] = 1.0;    // recursive formula    for (int i = 1; i <= N; i++) {        for (int j = 1; j <= k; j++) {            // (n,k) = p * (n-1,k-1) + (1-p) * (n-1,k)            b[i][j] = p * b[i-1][j-1] + (1.0 - p) *b[i-1][j];        }    }    return b[N][k];}