Binomials, the recursive way

exercise No. 111

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 289. 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 289, “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 289, “Pascal's triangle representing binomial coefficients.”.

Tasks:

  1. 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.

  2. 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.

  3. Reuse your unit tests from the lottery exercise.

A:

The implementation is surprisingly simple:

public static long binomial(int n, int k) {

  if (0 == k || n == k) { // End of recursion
    return 1;
  } else { // 0 < k  < n holds true, so continue reducing
    return binomial(n - 1, k) + binomial(n - 1, k - 1);
  }
}

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

Code
public static void main(String[] args) {

  long recursiveTime = 0, loopTime = 0;

  for (int i = 0; i < 10; i++) {
    {
      final long start = System.nanoTime();
      System.out.println(Binomial.binomial(90, 6));
      final long duration = (System.nanoTime() - start);
      recursiveTime += duration;
      System.out.println("Recursive: Elapsed time:" + duration);
    }
    {
      final long start = System.nanoTime();
      System.out.println(Binomial.binomialLoop(90, 6));
      final long duration = (System.nanoTime() - start);
      loopTime += duration;
      System.out.println("Loop: Elapsed time:" + duration);
    }
    System.out.println("           End of run #" + i +
                          " -------------------------------");
  }
  System.out.println("Aggregated loop time: " + loopTime);
  System.out.println("Aggregated recursion time: " + recursiveTime);
  System.out.println("Ratio Recursive / Loop: " +
                   (recursiveTime / loopTime));
}
Result
622614630
Recursive: Elapsed time:1801476567
622614630
Loop: Elapsed time:27028
           End of run #0 -------------------------------
622614630
Recursive: Elapsed time:1748821324
622614630
Loop: Elapsed time:22768
           End of run #1 -------------------------------
...
           End of run #9 -------------------------------
Aggregated loop time: 267557
Aggregated recursion time: 17539461906
Ratio Recursive / Loop: 65554

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

This is a typical result: Albeit providing elegant solutions recursion based implementations frequently fails when it comes to performance. Hence using recursion is often strongly discouraged. There are however situations where:

  1. The performance penalty is acceptable.

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