algorithm - 关于递归函数的推理

我正在学习罗伯特·塞吉威克和凯文·韦恩的第四版算法，并在练习1.1.27中被难住了，其中要求：
估计代码将使用的递归调用数

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

计算二项式（100，50）。
虽然我想帮忙回答这个问题，但我也希望能更好地理解和推理这些问题的一般性质，因此任何帮助或指针将不胜感激。

最佳答案

这个算法遍历帕斯卡三角形。
可以将三角形遍历排列为矩形n*k。如果算法只访问每个单元格一次，则总计为100*50=5000。
下面是一个例子：
在这个例子中，n=6，k=4。
然而，问题是算法不记得它已经访问了哪些单元格，所以它是冗余访问单元格。每次调用都会使调用次数加倍（糟糕，糟糕）。
所以它是1+2+4+8+16+32+…
2的幂和是2^（n+1）-1，所以它是2^101-1=2535301200456456458802993406410751
这是一个很大的数字。不要运行此程序。
（注意，这个数字是近似的，因为有些调用如果k＜0，则不加倍，所以可以把上面的数字除以2左右）。