Java编程二项分布的递归和非递归实现代码实例-创新互联

本文研究的主要内容是Java编程二项分布的递归和非递归实现，具体如下。

问题来源：

算法第四版 第1.1节 习题27：return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
计算递归调用次数，这里的递归式是怎么来的？

二项分布:

定义：n个独立的是/非试验中成功次数k的离散概率分布，每次实验成功的概率为p，记作B(n,p,k)。

概率公式：P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k)

其中C(n, k) = (n-k) !/(k! * (n-k)!)，记作ξ~B(n,p)，期望：Eξ=np，方差:Dξ=npq，其中q=1-p。

概率统计里有一条递归公式：

这个便是题目中递归式的来源。

该递推公式来自:C(n,k)=C(n-1,k)+C(n-1,k-1)。实际场景是从n个人选k个，有多少种组合？将着n个人按1~n的顺序排好，假设第k个人没被选中，则需要从剩下的n-1个人中选k个；第k个选中了，则需要从剩下的n-1个人中选k-1个。

书中二项分布的递归实现：

public static double binomial(int N, int k, double p) { 
    COUNT++; //记录递归调用次数 
    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); 
  }