用尾递归求解 "n-rooks"

Question

我正在尝试用尾递归解决 n 个 rooks 问题，因为它比标准递归更快，但我无法弄清楚如何使它全部工作。我查阅了这个问题背后的理论，发现解决方案是由一个叫做 "telephone numbers," 的东西给出的，它由等式给出：

其中 T(1) = 1 且 T(2) = 2。

我创建了一个递归函数来计算这个等式，但它只能快速运行到 T(40)，我需要它来计算 n > 1000 的位置，据我估计，目前这将需要数天的计算时间。

尾递归似乎是我最好的选择，但我希望这里的人可能知道如何使用尾递归来编程这种关系，因为我不太明白。

我正在使用 LISP，但愿意使用任何支持尾递归的语言

Answer 1

尾递归只是一个表示为递归的循环。

当你有一个 "forks" 的递归定义时，天真的实现很可能是时间指数，从 T(n) 到 T(n-1) 和 T(n-2)，然后T(n-2), T(n-3), T(n-3), T(n-4), 每一步计算加倍。

诀窍是反转计算，以便您从 T(1) 和 T(2) 开始构建。这只需要每一步的时间恒定，因此整体计算是线性的。

开始于

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

让我们使用 do 循环进行更新：

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

现在你只需要在达到你想要的时候停下来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)))

为了完整起见，请检查您的输入：

(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))))

此外，请编写测试并添加文档这是为了什么以及如何使用它。这尚未经过测试。

编写此尾递归时，您使用新值进行递归：

(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)))

当尾递归被优化时，它像循环一样缩放（但常数因子可能不同）。请注意，Common Lisp 不强制执行尾调用优化。

用尾递归求解 "n-rooks"

Solving "n-rooks" with tail recursion

recursion

lisp

common-lisp

tail-recursion

gnu-common-lisp