smallyu的博客
·
continuation 教程 (第一篇)：理解 CPS
内容提要
本文介绍了 continuation 的原理及其在编程中的应用，特别是通过递归和尾递归计算阶乘和斐波那契数列。通过示例代码阐释了 CPS（Continuation-Passing Style）的概念，强调了闭包在计算中的重要性，并指出理解这些内容需要扎实的基础知识。
关键要点
- 本文介绍了 continuation 的原理及其在编程中的应用。
- 强调了扎实的基础知识对于理解 continuation 的重要性。
- 递归函数 fact 的基本实现和尾递归形式的转换。
- CPS（Continuation-Passing Style）的概念及其在阶乘计算中的应用。
- 典型 CPS 形式的实现及其调用过程的拆解。
- CPS 的每一次调用使用闭包来储存当前步骤计算的值。
- 计算斐波那契数列的 fib 函数及其 CPS 形式的实现。
- CPS 形式的 fib 函数的复杂执行步骤拆解。
- 理解 CPS 是基础，后续可以利用 continuation 实现更多程序。
- 提到存在自动将代码转变为 CPS 形式的方法，但难度较大。
延伸问答
什么是 continuation 及其在编程中的应用？
Continuation 是一种编程概念，主要用于控制程序的执行流，特别是在递归和尾递归中。它通过传递一个函数来决定计算完成后的下一步操作。
如何实现阶乘的尾递归形式？
阶乘的尾递归形式可以通过增加一个参数来保存当前计算值，例如：function factTail(n, prod) { if (n == 0) { return prod; } else { return factTail(n-1, prod*n); } }
CPS（Continuation-Passing Style）是什么？
CPS 是一种编程风格，其中函数不直接返回结果，而是将结果传递给一个 continuation 函数，以决定后续的操作。
如何将递归函数转换为 CPS 形式？
将递归函数转换为 CPS 形式需要新增一个参数 k，表示 continuation 函数，计算结果通过调用 k 来返回，例如：function factCPS(n, k) { if (n == 0) { return k(1); } else { return factCPS(n-1, r => k(n * r)); } }
计算斐波那契数列的 CPS 实现是怎样的？
斐波那契数列的 CPS 实现通过将两个递归调用嵌套在一个 continuation 函数中，例如：function fibCPS(n, k) { if (n == 0) { return k(0); } else if (n == 1) { return k(1); } else { return fibCPS(n-1, r1 => fibCPS(n-2, r2 => k(r1 + r2))); } }
理解 CPS 需要哪些基础知识？
理解 CPS 需要扎实的基础知识，特别是对递归、尾递归和闭包的理解，这些是掌握更复杂概念的前提。
