1

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

电话/N-rooks 关系

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

我创建了一个递归函数来评估这个方程，但它只能在 T(40) 之前快速工作，我需要它来计算 n > 1000 的位置，目前据我估计需要数天的计算时间。

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

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

4

1 回答 1

3

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

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

于 2016-05-04T00:33:19.673 回答