Binomial Coefficient Recursion:
The Good, and The Bad and Ugly
Published in inroads (bulletin of the ACM SIG on Computer Science Education) Vol 33, No. 2 (June 2001), pp. 35–36.
Click here for a Word-97 version of this paper.
Click here for the PDF version of the paper from the journal. — a font foul-up printed the yen currency symbol (¥) for the raised dot (·).
The binomial coefficient (or, alternatively, the number of combinations of n items taken k at a time), provides two defining recurrences. One of these provides a very useful recursive function — a very good way for a program to calculate this function — while the other provides a very wasteful recursive function — the balancing bad and ugly way.
The Bad and Ugly Recursion
First let us consider the "bad and ugly" recursion: this is derived from the recurrence we get if we define the binomial coefficient in terms of Pascal's Triangle: each binomial coefficient that is not on the boundary of the triangle (that is, n > k > 0) is the sum of the two term immediately above it in the triangle.
n=0: 1 n=1: 1 1 n=2: 1 2 1 n=3: 1 3 3 1 n=4: 1 4 6 4 1 . . .
To write the recurrence, though, it is convenient to write the triangle not as an isosceles triangle, but as a right triangle (that is, with a flush left margin and ragged right margin).
n=1: 1 1
n=2: 1 2 1
n=3: 1 3 3 1
n=4: 1 4 6 4 1
. . .
On this basis, Pascal's Triangle gives the following recurrence:
As a recursive formula, however, this has the highly undesirable characteristic that it calls itself twice in the recursion. Another way of seeing how undesirable this is as a recursive function is to note that it generates the binomial coefficient by finding the ones on the boundary of Pascal's Triangle and adding them together. Explicit measurement shows that the computation of C(n, k) will require 2*C(n, k) — 1 function calls — rather wasteful even for C(15, 8) = 6435 (which would require 12,869 function calls). [One can indeed prove inductively that the number of function calls is 2*C(n, k) – 1, but to keep this short the proof is left as an "exercise for the reader."]
The Good Recursion
This recursion comes from considering the calculating formula for binomial coefficients:
It is useful, though, to remember that really represents the highest k terms of n!:
n · (n – 1) · (n – 2) · (n – 3) · · · (n – k + 1) — k terms in all.
Similarly, k! is also k terms long:
k · (k – 1) · (k – 2) · (k – 3) · · · 1
(where both top and bottom have k entries). This can be reorganized in terms of recurrences as
being sure to actually compute as C(n,k) = ( C(n–1, k–1) · n ) / k
This recurrence provides a computationally useful formula for binomial coefficients with n of any size. Even though C(n,k) may be a fairly small number, the separate calculation of the numerator and denominator would require extended precision arithmetic, something not required in the alternating multiplication and division given through the recurrence relationship. While there are k+1 function calls, one can guarantee at most n/2 function calls by taking advantage of the equality C(n, k) = C(n, n–k)
Dr. Ray Hamel of my department suggests that one may wish to avoid ever having an intermediate result of magnitude larger than the final result: one can simply divide before multiplying (though at the computation expense of finding the greatest common divisor):
Let d = gcd( n, k ), and let q = k / d — where "gcd" denotes the greatest common divisor.
C( n, k ) = ( C( n–1, k–1 ) / q ) · ( n / d )
I wish to thank Dr. Ray Hamel for insightful comments on this note, and specifically for the above formulation as a product of two integer quotients.