#### Binomials, the recursive way

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:

Each inner node within the triangle is the sum of its two upper left and right neighbours. With respect to a recursive definition Figure 283, “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 283, “Pascal's triangle representing binomial coefficients.”.

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

4. Reuse your unit tests from the lottery exercise.

5. Compare your recursive implementation's performance with a loop based implementation using System.nanoTime().

A:

The recursive implementation is surprisingly simple:

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 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)); } 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 (maybe the only) way to implement a desired logic.