关于递归函数的推理

Question

我正在研究罗伯特·塞奇威克和凯文·韦恩的第四版"算法",并参加了练习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).

虽然我想帮助回答这个问题,但我也希望能够更好地理解和推理这种性质的问题,所以任何帮助或指示都会受到赞赏.

Answer 1

该算法遍历Pascal的三角形.

您可以将三角形遍历排列为矩形N*K.如果算法仅访问每个单元格一次,则总计为100*50 = 5000.

这是一个例子:

在这个例子中,N = 6,K = 4.

然而,问题是该算法不记得它已访问过哪些单元,因此它冗余地访问单元.每次通话都会减少通话次数(哎呀,坏).

所以它是1 + 2 + 4 + 8 + 16 + 32 + ......

2的幂的总和是2 ^(n + 1)-1,所以它将是2 ^ 101 - 1 = 2535301200456458802993406410751

这是一个很大的数字.不要运行这个程序.

(注意,这个数字只是近似值,因为如果K <0,某些调用不会加倍,所以上面的数字可能除以2左右).