Binomials, the recursive way

exercise No. 116

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 296. 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 296, “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 296, “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 
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 fail with respect to performance. Hence using recursion is often strongly discouraged. There are however situations where:

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