有两个累积变量的tco模式吗？

Question

只是为了好玩(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来说非常慢。

我真的不知道如何将这个函数转换成一个可以进行尾叫优化的版本。我看到了一个使用斐波那契数两个累积变量的模式，但未能将该模式转换为我的函数。

如何将复杂的递归转换为tco版本，或者是否应该直接实现迭代解决方案？

Answer 1

首先，请注意，记忆化可能是优化代码的最简单方法:它不会逆转操作流程；您可以用给定的k调用函数，然后返回到零来计算前面的值，而是使用缓存。但是，如果您想用TCO将函数从递归转换为迭代，则必须从零到k计算事物，并假装您有一个固定大小的堆栈/内存。

阶跃函数

首先，编写一个计算给定k、n-1和n-2的当前n的函数。

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

带有递归(迭代)调用的修改函数

现在，您需要从k开始调用n，从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中注入尾递归调用时，可能会稍微困难，或者使您的代码难以阅读。我认为最好用循环代替，因为：

1. 与尾递归调用不同，您可以保证代码将按照您的意愿运行，而不必担心实现是否会真正优化尾调用。
2. step函数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)))

如何将复杂的递归转换为tco版本，或者是否应该直接实现迭代解决方案？

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

亦见

Scheme的名叫莱特、公共Lisp中的重覆宏和Clojure中的重现特殊形式。