recursion - 用尾递归解决 "n-rooks"

Question

我试图用尾递归解决 n 个 rooks 问题，因为它比标准递归更快，但我无法弄清楚我们如何让它全部工作。我查阅了这个问题背后的理论，发现解决方案是由称为“电话号码”的东西给出的，它由以下等式给出:

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

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

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

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

Answer 1

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

当你有一个“ fork ”的递归定义时，天真的实现很可能是时间指数，从 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 不强制执行尾调用优化。