是否存在具有两个累积变量的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数字,但无法将此模式转换为我的函数.

是否有一般指导如何将复杂的递归转换为tco版本,或者我应该直接实现迭代解决方案.

Answer 1

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

\n

步进功能

\n

首先，编写一个函数，在给定k、n-1和n-2的情况下计算当前 n：

\n

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

\n

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

\n

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

\n

现在，您需要n从 k 从 0 开始调用，直到您想要计算的最大值（ m如下所示）。因此，我将添加一个参数m，它控制递归调用何时停止，并n使用修改后的参数进行递归调用。您可以看到参数已转移，当前n1是下一个n2，等等。

\n

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

\n

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

\n

(defun g (m)\n  (f m 0 0 0))\n

\n

该函数的跟踪呈现出箭头“>”形状，尾递归函数就是这种情况（跟踪可能会抑制尾调用优化）：

\n

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

\n

带循环的驱动程序函数

\n

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

\n

\n
1. 与尾递归调用不同，您可以保证代码将按照您的意愿运行，而不必担心您的实现是否会真正优化尾调用。
\n
2. 步骤函数的代码n更简单，仅表达正在发生的事情，而不是详细说明如何发生发生（尾递归调用只是这里的实现细节）。
\n

\n

通过上面的函数n，你可以改变g：

\n

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

\n

\n

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

\n

\n

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

\n

\xc2\xa0另请参阅

\n

Scheme 的名称为 let， Common Lisp 中的RECUR宏以及Clojure 中的recur特殊形式。

\n