Solving "n-rooks" with tail recursion

Question

Im trying to solve the n rooks problem with tail recursion since it is faster than standard recursion, but am having trouble figuring our how to make it all work. I've looked up the theory behind this problem and found that the solution is given by something called "telephone numbers," which are given by the equation:

where T(1) = 1 and T(2) = 2.

I have created a recursive function that evaluates this equation but it only works quickly up to T(40), and I need it to calculate where n > 1000, which currently by my estimates will take days of computation.

Tail recursion seems to be my best option, but I was hoping someone here might know how to program this relation using tail recursion, as I don't really understand it.

I'm working in LISP, but would be open to using any language that supports tail recursion

Answer 1

Tail recursion is just a loop expressed as recursion.

When you have a recursive definition that "forks", the naive implementation is most likely exponential in time, going from T(n) to T(n-1) and T(n-2), then T(n-2), T(n-3), T(n-3), T(n-4), doubling the computation at each step.

The trick is reversing the computation so that you build up from T(1) and T(2). This just needs constant time at each step so the overall computation is linear.

Start with

(let ((n 2)
      (t-n 2)
      (t-n-1 1))
  …)

Let's use a do loop for updating:

(do ((n 2 (1+ n))
     (t-n 2 (+ t-n (* n t-n-1)))
     (t-n-1 1 t-n))
  …)

Now you just need to stop when you reach your desired n:

(defun telephone-number (x)
  (do ((n 2 (1+ n))
       (t-n 2 (+ t-n (* n t-n-1)))
       (t-n-1 1 t-n))
      ((= n x) t-n)))

To be complete, check your inputs:

(defun telephone-number (x)
  (check-type x (integer 1))
  (if (< x 3)
      x
      (do ((n 2 (1+ n))
           (t-n 2 (+ t-n (* n t-n-1)))
           (t-n-1 1 t-n))
          ((= n x) t-n))))

Also, do write tests and add documentation what this is for and how to use it. This is untested yet.

When writing this tail recursive, you recurse with the new values:

(defun telephone (x)
  (labels ((tel-aux (n t-n t-n-1)
             (if (= n x)
                 t-n
                 (tel-aux (1+ n)
                          (+ t-n (* n t-n-1))
                          t-n))))
    (tel-aux 2 2 1)))

When tail recursion is optimized, this scales like the loop (but the constant factor might differ). Note that Common Lisp does not mandate tail call optimization.