Reasoning About Recursive Functions

Question

I'm working through the fourth edition of Algorithms by Robert Sedgewick and Kevin Wayne and am stumped on exercise 1.1.27 which asks:

Estimate the number of recursive calls that would be used by the code

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);
}

to compute binomial(100, 50).

Although I'd like like help answering this question, I'd also like to get better at understanding and reasoning about questions of this nature in general and so any help or pointers would be appreciated.

Answer 1

This algorithm traverses Pascal's triangle.

You can arrange the triangle traversal as a rectangle N * K. If the algorithm visits every cell only once, then total is 100 * 50 = 5000.

Here is an example:

In this example N=6 and K=4.

However, the problem is that the algorithm does not remember what cells it already visited so it is redundantly visiting cells. Each call DOUBLES the number of calls (oops, bad).

So it goes 1 + 2 + 4 + 8 + 16 + 32 + ...

The sum of powers of 2 is 2^(n+1)-1, so it would be 2^101 - 1 = 2535301200456458802993406410751

That is a big number. Do not run this program.

(Note that the number is only approximate because some calls do not double if K<0, so it may the above number divided by 2 or so).

Answer 2

You'll see the pattern right away if you start with concrete examples. For N=0, obviously it's 0. For N=1, it's 2 recursive calls (because each call yields two recursive call at the directly inferior level, i.e. for N-1.

For N=2, then it's 2*2 = 4

For N=3, then it's 2*2*2 (i.e. 2^3)

For N=4, then it's 2^4

I'm assuming you see the pattern.