在用功能语言编写用于记忆和继续传递样式（CPS）功能的示例时，我最终都使用了Fibonacci示例。但是，斐波那契并没有真正从CPS中受益，因为循环仍然必须按指数规律地运行，而使用记忆仅是第一次O（n），随后每次都是O（1）。
将CPS和备忘录结合使用对于Fibonacci来说有一点好处，但是是否有示例表明CPS是防止您用尽堆栈并提高性能的最佳方法，而备忘录不是解决方案？
或：是否有任何何时选择一个准则的指南？
最佳答案
在CPS上
尽管CPS在编译器中可用作中间语言，但在源语言级别上，它主要是一种设备，用于（1）编码复杂的控制流（与性能无关）和（2）转换非尾调用的堆栈空间到一个连续分配的尾调用消耗堆空间中。例如，当您编写（未经测试的代码）时
let rec fib = function
| 0 | 1 -> 1
| n -> fib (n-1) + fib (n-2)
let rec fib_cps n k = match n with
| 0 | 1 -> k 1
| n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b)))
先前分配了新堆栈帧的非尾调用
fib (n-2)变为尾调用fib (n-2) (fun b -> k (a+b))，后者分配了闭包fun b -> k (a+b)（在堆上）以将其作为参数传递。这不会渐进地减少程序的内存使用（可能会进行某些特定于域的进一步优化，但这是另一回事了）。您只是用堆栈空间来交换堆空间，这在操作系统严重限制了堆栈空间的系统上很有趣（对于某些ML实现（例如SML / NJ）则不是这样，它们会在堆上而不是在堆栈上跟踪其调用堆栈）使用系统堆栈），并且由于额外的GC成本和潜在的本地性降低而可能降低性能。
CPS转换不太可能改善性能（尽管您的实现和运行时系统的详细信息可能会这样做），并且它是一种普遍适用的转换，它可以避免通过深度调用堆栈避免递归函数的“堆栈溢出”。
关于记忆
记忆化对于引入共享递归函数的子调用很有用。递归函数通常通过将其分解成几个严格更简单的“子问题”（递归子调用）来解决“问题”（“
n的计算斐波那契”等），在某些基本情况下可以解决该问题马上。对于任何递归函数（或问题的递归表述），您都可以观察子问题空间的结构。
Fib(k)需要哪个更简单的Fib(n)实例返回其结果？这些实例又需要哪个更简单的实例？在一般情况下，子问题的空间是一个图（出于终止目的，通常是非循环的）：有些节点具有多个父节点，这是它们属于子问题的几个不同的问题。例如，
Fib(n-2)是Fib(n)和Fib(n-2)的子问题。此图中的节点共享数量取决于特定的问题/递归函数。对于斐波那契，所有节点在两个父节点之间共享，因此存在很多共享。没有备注的直接递归调用将无法观察到此共享。递归函数的调用结构是一棵树，而不是图，并且共享的子问题（例如
Fib(n-2)）将被完全访问几次（与图中从起始节点到子问题节点的路径一样多）。 。记忆化通过让一些子调用直接返回“我们已经计算出此节点，这就是结果”来引入共享。对于有很多共享的问题，这可能会导致（无用的）计算量大大减少：引入备忘录后，斐波那契从指数复杂度变为线性复杂度–请注意，还有其他编写函数的方法，而无需使用备忘录，但是不同的子调用结构，具有线性复杂度。let rec fib_pair = function
| 0 -> (1,1)
| n -> let (u,v) = fib_pair (n-1) in (v,u+v)
使用某种形式的共享（通常通过存储结果的大表）来避免子计算的无用重复的技术在算法界是众所周知的，称为Dynamic Programming。当您意识到问题适合这种处理时（您注意到子问题之间的共享），这可以带来很大的性能优势。
比较有意义吗？
两者似乎大多彼此独立。
存在很多不适用记忆的问题，因为子问题图结构没有任何共享（它是一棵树）。相反，CPS转换适用于所有递归函数，但本身并不能带来性能优势（除了潜在的常数因素（由于所使用的特定实现和运行时系统，尽管它们很可能会编写代码）慢而不是快）。
通过检查非尾部上下文来提高性能
有一些与CPS相关的优化技术可以提高递归函数的性能。它们包括在递归调用（将其转换为简单的CPS样式的函数）之后查看“尚待完成”的计算，并为其找到替代的更有效的表示形式，这不会导致系统的闭包分配。考虑例如：
let rec length = function
| [] -> 0
| _::t -> 1 + length t
let rec length_cps li k = match li with
| [] -> k 0
| _::t -> length_cps t (fun a -> k (a + 1))
您会注意到，非递归调用的上下文
[_ + 1]具有简单的结构：它添加了一个整数。除了将其表示为函数fun a -> k (a+1)之外，您还可以存储与该函数的多个应用相对应的要添加的整数，使k成为整数而不是函数。let rec length_acc li k = match li with
| [] -> k + 0
| _::t -> length_acc t (k + 1)
此函数在恒定而不是线性的空间中运行。通过将尾部上下文的表示形式从函数转换为整数，我们消除了使内存使用线性化的分配步骤。
仔细检查加法顺序将发现它们现在是按不同的方向执行的：我们首先将与列表开头相对应的1进行加法，而
cps版本则将其最后加法。此顺序反转有效，因为_ + 1是关联操作（如果有多个嵌套上下文foo + 1 + 1 + 1，则可以从内部((foo+1)+1)+1或外部foo+(1+(1+1))开始计算它们）是有效的。 。上面的优化可用于非尾调用周围的所有此类“关联”上下文。当然，基于相同的想法还有其他优化可用（我不是这种优化的专家），这是要查看所涉及的连续结构，并以比分配给堆的函数更有效的形式表示它们。
这与“去功能化”的转换有关，该转换将连续性的表示形式从函数更改为数据结构，而不改变内存消耗（当在原始程序中分配了闭包时，去功能化的程序将分配数据节点），但是可以用一阶语言（没有一流的功能）表达尾递归CPS版本，并且在数据结构和模式匹配比闭包分配和间接调用更有效的系统上可以更高效。
type length_cont =
| Linit
| Lcons of length_cont
let rec length_cps_defun li k = match li with
| [] -> length_cont_eval 0 k
| _::t -> length_cps_defun t (Lcons k)
and length_cont_eval acc = function
| Linit -> acc
| Lcons k -> length_cont_eval (acc+1) k
let length li = length_cps_defun li Linit
type fib_cont =
| Finit
| Fminus1 of int * fib_cont
| Fminus2 of fib_cont * int
let rec fib_cps_defun n k = match n with
| 0 | 1 -> fib_cont_eval 1 k
| n -> fib_cps_defun (n-1) (Fminus1 (n, k))
and fib_cont_eval acc = function
| Finit -> acc
| Fminus1 (n, k) -> fib_cps_defun (n-2) (Fminus2 (k, acc))
| Fminus2 (k, acc') -> fib_cont_eval (acc+acc') k
let fib n = fib_cps_defun n Finit
关于f# - 在继续传递样式和备注之间进行选择，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14781875/