只是为了好玩(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 版本,或者我应该直接实现迭代解决方案。?
最佳答案
首先,请注意,记忆化可能是优化代码的最简单方法:它不会反转操作流程;你用给定的 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 和 k 的情况下计算 n 的部分。具有递归(迭代)调用的修改函数
现在,您需要调用
n
从 k 开始,从 0 到要计算的最大值,命名为 m
此后。因此,我将添加一个参数 m
,它控制递归调用何时停止,并调用 n
递归地使用修改后的参数。您可以看到参数被转移,当前 n1
是下一个n2
, ETC。(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
中注入(inject)尾递归调用时,可能会有点困难,或者使您的代码难以阅读。 .我认为最好使用循环,因为: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 , RECUR Common Lisp 中的宏和 recur Clojure 中的特殊形式。
关于recursion - 是否存在具有两个累积变量的 tco 模式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45663503/