是否存在具有两个累积变量的 tco 模式？

Question

纯属娱乐(Project Euler #65)我想实现公式

n_k = a_k*n_k-1 + n_k-2

以一种高效的方式。 a_k 是 1 或 (* 2 (/ k 3))，取决于 k.

我从递归解决方案开始：

(defun numerator-of-convergence-for-e-rec (k)
  "Returns the Nth numerator of convergence for Euler's number e."
  (cond ((or (minusp k)) (zerop k) 0)
        ((= 1 k) 2)
        ((= 2 k) 3)
        ((zerop (mod k 3)) (+ (* 2 (/ k 3) (numerator-of-convergence-for-e-rec (1- k)))
                              (numerator-of-convergence-for-e-rec (- k 2))))
        (t (+ (numerator-of-convergence-for-e-rec (1- k))
              (numerator-of-convergence-for-e-rec (- k 2))))))

对小的 k 有效，但对 k = 100 显然很慢。

我真的不知道如何将此函数转换为可以进行尾调用优化的版本。我已经看到一个使用两个累加变量的模式 fibonacci numbers 但未能将此模式转换为我的函数。

是否有关于如何将复杂递归转换为 tco 版本的通用指南，或者我应该直接实施迭代解决方案吗？

Answer 1

首先，请注意，记忆可能是优化代码的最简单方法：它不会反转操作流程；你用给定的 k 调用你的函数，它返回到零来计算以前的值，但有一个缓存。但是，如果你想使用 TCO 将你的函数从递归转换为迭代，你将不得不计算从零到 k 的东西，并假装你有一个恒定大小的堆栈/内存。

步进函数

首先，写一个函数计算电流 n 给定 k, n-1和 n-2:

(defun n (k n1 n2)
  (if (plusp k)
      (case k
        (1 2)
        (2 3)
        (t (multiple-value-bind (quotient remainder) (floor k 3)
             (if (zerop remainder)
                 (+ (* 2 quotient n1) n2)
                 (+ n1 n2)))))
      0))

这一步应该很简单；在这里，我稍微重写了你的函数，但实际上我只提取了计算 n 的部分，给定之前的 n 和 k .

使用递归（迭代）调用修改函数

现在，你需要调用n从k开始，从0开始到你要计算的最大值，以下命名为m。因此，我将添加一个参数 m，它控制递归调用何时停止，并使用修改后的参数递归调用 n。您可以看到参数发生了变化，当前 n1 是下一个 n2，等等

(defun f (m k n1 n2)
  (if (< m k)
      n1
      (if (plusp k)
        (case k
          (1 (f m (1+ k) 2 n1))
          (2 (f m (1+ k) 3 n1))
          (t (multiple-value-bind (quotient remainder) (floor k 3)
           (if (zerop remainder)
             (f m (1+ k) (+ (* 2 quotient n1) n2) n1)
             (f m (1+ k) (+ n1 n2) n1)))))
        (f m (1+ k) 0 n1))))

仅此而已，只是您不想向用户显示此界面。实际函数 g 正确引导对 f:

的初始调用

(defun g (m)
  (f m 0 0 0))

此函数的跟踪显示箭头“>”形状，这是尾递归函数的情况（跟踪可能会抑制尾调用优化）：

  0: (G 5)
    1: (F 5 0 0 0)
      2: (F 5 1 0 0)
        3: (F 5 2 2 0)
          4: (F 5 3 3 2)
            5: (F 5 4 8 3)
              6: (F 5 5 11 8)
                7: (F 5 6 19 11)
                7: F returned 19
              6: F returned 19
            5: F returned 19
          4: F returned 19
        3: F returned 19
      2: F returned 19
    1: F returned 19
  0: G returned 19
19

带循环的驱动函数

当我们在原始函数中注入尾递归调用时，可能会有些困难，或者让您的代码难以阅读的部分 n。我认为最好使用循环代替，因为：

与尾递归调用不同，您可以保证代码按您希望的方式运行，而不必担心您的实现是否真的会优化尾调用。
步进函数n的代码更简单，只表达发生了什么，而不是详细说明如何（尾递归调用只是这里的一个实现细节。

通过上面的函数n，可以把g改成：

(defun g (m)
  (loop
     for k from 0 to m
     for n2 = 0 then n1
     for n1 = 0 then n
     for n = (n k n1 n2)
     finally (return n)))

Is there a general guideline how to transform complex recursions to tco versions or should I implement an iterative solution directly?

找到一个将计算从基本情况推进到一般情况的阶梯函数，并将中间变量作为参数，特别是过去调用的结果。此函数可以调用自身（在这种情况下它将是尾递归的，因为您必须首先计算所有参数），或者只是在循环中调用。计算初始值时必须小心，与简单的递归函数相比，你可能有更多的极端情况。

另请参阅

方案的 named let, the RECUR macro in Common Lisp and the recur Clojure 中的特殊形式。

是否存在具有两个累积变量的 tco 模式？

Is there a tco pattern with two accumulating variables?

recursion

common-lisp

tail-call-optimization

步进函数

使用递归（迭代）调用修改函数

带循环的驱动函数

另请参阅