Binomials, the recursive way

exercise No. 122

Q:

With respect to the upcoming tic-tac-toe strategy exercise we provide a second example of a recursively defined method. Our binomial coefficients from our lottery exercise may be computed in a recursive fashion. Consider pascal's triangle:

Figure 310. Pascal's triangle representing binomial coefficients.
Pascal's triangle representing binomial coefficients.

Each inner node within the triangle is the sum of its two upper left and right neighbours. With respect to a recursive definition Figure 310, “Pascal's triangle representing binomial coefficients.” tells us:

Reducing statement

∀ 0 < k < n : ( n + 1 k + 1 ) = ( n k + 1 ) + ( n k ) .

This equation is actually a straightforward exercise by simply adding two fractions. Wanna try?

Termination condition

( n 0 ) = ( n n ) = 1 .

NB: These values show up along the left and right edge in Figure 310, “Pascal's triangle representing binomial coefficients.”.

Tasks:

  1. Re-use unit tests from your lottery exercise.

  2. Re-implement public static long binomial(int n, int k) in a recursive fashion as outlined above.

    Tip

    This is surprisingly simple. You may want to consider reading external resources dealing with the subject of recursively implemented methods.

  3. Compare the performance of your recursive implementation and the traditional loop based approach. The “6 out of 90” lottery is a good starting point.

    Tip

    The standard methods currentTimeMillis() and nanoTime allow for measuring method execution by means of subtracting time stamp values prior and after execution. “See How to calculate elapsed / execute time in Java”.

A:

The recursive implementation simply reads:

public static long binomial(int n, int k) { // Safely assuming 0 < k < n

  if (0 == k || n == k) {          // Termination condition
    return 1;
  } else {                         // Reducing statement
    return binomial(n - 1, k) +
           binomial(n - 1, k - 1);
  }
}

For the purpose of performance comparison we rename the “traditional” loop based implementation to become static public long binomialLoop(int n, int k) and add a performance test:

Code 
long recursiveTime = 0, loopTime = 0;

for (int run = 0; run <= 10; run++) {
  {
    final long start = System.nanoTime();
    System.out.format("Recursive result: %d\n", Binomial.binomial(90, 6));
    final long duration = (System.nanoTime() - start);
    recursiveTime += duration;
    System.out.println("    Elapsed time:" + duration);
  }
  {
    final long start = System.nanoTime();
    System.out.format("     Loop result: %d\n", Binomial.binomialLoop(90, 6));
    final long duration = (System.nanoTime() - start);
    loopTime += duration;
    System.out.println("    Elapsed time:" + duration);
  }
  System.out.format("End of run #%d -------------------------------\n\n", run);
}
System.out.println("Aggregated recursion time: " + recursiveTime);
System.out.println("     Aggregated loop time: " + loopTime);
System.out.println("   Ratio Recursive / Loop: " + (1. * recursiveTime / loopTime));
Result 
...
End of run #9 -------------------------------

Recursive result: 622614630
    Elapsed time: 1691967305
     Loop result: 622614630
    Elapsed time: 42557
End of run #10 -------------------------------

Aggregated recursion time: 18666605910
     Aggregated loop time: 520035
   Ratio Recursive / Loop: 35894.903054602095

From a performance point of view this result is quite disillusioning: The loop based implementation is on average ~36000 times faster compared to the recursive approach.

This is a typical result: Albeit providing elegant solutions recursion based implementations frequently offer extremely poor performance discouraging its usage. There are however situations where:

  1. A performance penalty is acceptable.

  2. Recursion is the only (known) way to implement a desired logic.

Prev  Up  Next
Factorial, the recursive way  Home  Implementing exponentials.