Binomial Coefficient using Tail Recursion in LISP

Question

I want to program a function to find C(n,k) using tail recursion, and I would greatly appreciate your help.

I have reached this:

(defun tail-recursive-binomial (n k)
  (cond ((or (< n k) (< k 0)) NIL)
        ((or (= k 0) (= n k)) 1)
        (T (* (tail-recursive-binomial (- n 1) (- k 1)) (/ n k)))))

Using the following property of the binomial coefficients.

But I don't know how to make the recursive call to be the last instruction executed by each instance, since there the last one is the product. I have been trying it by using an auxiliary function, which I think is the only way, but I haven't found a solution.

Fred Foo Fred Foo · Accepted Answer · 2010-10-31T13:11:10

As starblue suggests, use a recursive auxiliary function:

(defun binom (n k)
  (if (or (< n k) (< k 0))
    NIL  ; there are better ways to handle errors in Lisp
    (binom-r n k 1)))

;; acc is an accumulator variable
(defun binom-r (n k acc)
  (if (or (= k 0) (= n k))
    acc
    (binom-r (- n 1) (- k 1) (* acc (/ n k)))))

Or, give the main function an optional accumulator argument with a default value of 1 (the recursive base case):

(defun binom (n k &optional (acc 1))
  (cond ((or (< n k) (< k 0)) NIL)
        ((or (= k 0) (= n k)) acc)
        (T (binom (- n 1) (- k 1) (* acc (/ n k))))))

The latter option is slightly less efficient, since the error condition is checked in every recursive call.

Binomial Coefficient using Tail Recursion in LISP

2 Answers