这是一个 continuation 系列教程：
我们来由浅入深地系统学习下 continuation 的原理以及应用场景。这个系列教程的内容和王垠的 continuation 专项班无关，是我自己学习和研究的成果，所以不会有版权问题。不过当然正是因为我学习了基础班，打下了坚实的基础，才知道该如何去自学和理解 continuation 这个概念。这篇文章会少量透露出基础班学到的技能，毕竟 continuation 属于基础班的进阶内容，无法跳过基础技能去理解。
首先用递归的形式写一个阶乘函数 fact，我们已经很熟悉它的写法，不需要过多解释：
function fact(n)
{
if (n === 0)
{
return 1;
}
else
{
return n * fact(n - 1);
}
}
console.log("fact1=", fact(1)); // 1
console.log("fact3=", fact(3)); // 6
console.log("fact5=", fact(5)); // 120
接着把 fact 函数改为尾递归的形式。尾递归会比递归多一个参数，新参数用来保存每个调用计算后的值：
function factTail(n, prod)
{
if (n == 0)
{
return prod;
}
else
{
return factTail(n-1, prod*n);
}
}
console.log("factTail1=", factTail(1, 1)); // 1
console.log("factTail3=", factTail(3, 1)); // 6
console.log("factTail5=", factTail(5, 1)); // 120
我们基于 fact 函数的尾递归形式，再新增一个参数 k，这个 k 是一个函数，fact 不直接返回计算后的值，而是结果值对 k 函数的调用，像这样：
function factTailCPS(n, prod, k)
{
if (n == 0)
{
return k(prod);
}
else
{
return factTailCPS(n-1, prod*n, k);
}
}
factTailCPS( 1, 1, x => console.log("factTailCPS1=", x) ); // 1
factTailCPS( 3, 1, x => console.log("factTailCPS1=", x) ); // 6
factTailCPS( 5, 1, x => console.log("factTailCPS1=", x) ); // 120
这个 k 就是 continuation，意味着告诉 fact 函数，你执行完了计算出结果之后，应该如何进行下一步延续。不用怀疑，这个函数完全符合 CPS（Continuation-Passing-Style）的形式。
但是用尾递归结合 continuation 参数的形式，显然不够简洁，并不算典型的 CPS 形式。典型的 CPS 形式比较难理解，所以不需要自己思考出来，直接看这个现成的例子，我们对递归形式的 fact 函数改进一下：
function factCPS(n, k)
{
if (n == 0)
{
return k(1);
}
else
{
return factCPS(n-1, r => k(n * r));
}
}
可能看着有点懵，不要慌，我们拆解一下其中的内容。首先 k 仍然代表 continuation，并且 k 是一个函数。然后我们这样来调用：
let factCPS1 = factCPS(0, x => x);
console.log("factCPS1=", factCPS1); // 1
let factCPS3 = factCPS(3, x => x);
console.log("factCPS3=", factCPS3); // 6
let factCPS5 = factCPS(5, x => x);
console.log("factCPS5=", factCPS5); // 120
关键在于调用的时候，传入函数的第二个参数是 x => x，如果结合函数内部的 r => k(n * r)，也许一下子就糊涂了。
这确实是最难理解的部分。我们以计算 2 的阶乘为例，写一个拆解 factCPS 函数调用步骤的过程。这里用到的技巧是在基础班第一课就学过的 单步替换，对于理解递归非常有帮助。如果在基础班经过训练并且打好基础，确实会有助于理解更复杂的东西，比如这里的 CPS 调用：
let factCPS2 = factCPS(2, x => x);
console.log("factCPS2=", factCPS2); // 2
// n=2, k=x=>x, return factCPS(1, r => k(2 * r));
// n=1, k=r=>(x=>x)(2*r), return factCPS(0, r => k(1 * r));
// n=0, k=r=>(r=>(x=>x)(2*r)(1*r)), return k(1);
// k(1) = r=>(x=>x)(2*r)(1*1)
// = (x=>x)(2)
// = 2
虽然我已经按照正确的思路拆解出了正确的步骤，但是从阅读者的角度，这仍然会非常难理解，可以自己拆解一下试试，逐步理解典型 CPS 的调用过程。理解这些步骤也许需要几个小时的时间，这是正常的。
总结来说，CPS 的每一次调用，都是在用闭包来储存当前步骤计算的值。尾递归是直接用参数传递值，而 CPS 是在用闭包传递给下个步骤值，就是这样的关系。当然理解这一点的前提是，知道闭包是什么，这个也是基础班学习的重点内容，尤其是会在实现解释器环节，自己实现闭包的语句，对于闭包的理解会很透彻。
计算阶乘的函数 fact 特点是只在函数体内进行一次递归调用，我们再来看计算斐波那契数列的 fib 函数，它会在函数体内进行两次递归调用，CPS 该怎么处理这个情况。
fib 函数的递归形式的定义是这样：
function fib(n)
{
if (n == 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else
{
return fib(n-1) + fib(n-2);
}
}
console.log("fib(2)=", fib(2)); // 1
console.log("fib(5)=", fib(5)); // 5
这里直接给出 fib 函数的 CPS，然后理解一下 fib 函数的运作过程：
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 是把另一次递归调用，写在了原本的 r => k(r) 函数里，让第二次内部调用成为了递归调用 fib 时候的子调用。这句话有点绕，可以结合代码理解一下。
CPS 形式的 fib 函数这样来调用：
let fibCPS1 = fibCPS(1, x=>x);
console.log("fibCPS1=", fibCPS1); // 1
let fibCPS2 = fibCPS(2, x=>x);
console.log("fibCPS2=", fibCPS2); // 1
let fibCPS4 = fibCPS(4, x=>x);
console.log("fibCPS4=", fibCPS4); // 3
let fibCPS5 = fibCPS(5, x=>x);
console.log("fibCPS5=", fibCPS5); // 5
我们以计算 3 的斐波那契数为例，拆解一下具体的执行步骤。要注意的是，这个过程非常复杂，比 fact 函数还要复杂很多，只有自己亲自写一下才能搞清楚：
let fibCPS3 = fibCPS(3, x=>x);
console.log("fibCPS3=", fibCPS3); // 1+1=2
// n=3, k=x=>x,
// return fibCPS(2, r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) );
// n=2, k= r1 => fibCPS(1, r2=>(x=>x)(r1+r2)),
// return fibCPS(1, r1 => fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(r1+r2)) );
// n=1, k= r1 => fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(r1+r2)),
// return k(1)
// return ( r1 => fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(r1+r2)) )(1)
// return fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(1+r2))
// n=0, k= r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(1+r2)
// return k(0)
// return ( r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(1+r2) )(0)
// return ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) ) (1+0)
// return fibCPS(1, r2=>(x=>x)(1+r2))
// n=1, k = r2=>(x=>x)(1+r2)
// return k(1)
// return (x=>x)(1+1)
// return 2
那么经过了 fact 和 fib 函数的训练，我们就已经知道 CPS 的形式是什么，以及具体的执行步骤是怎样了。理解 CPS 只是开始，接下来还会利用 continuation 实现更多有趣的程序。
已知一个递归形式的 sumFrom 函数，接收两个参数 a 和 b，函数的功能是计算 a+(a+1)+...+(b-1)+b 的值，例如参数是 1 和 4，则计算 1+2+3+4 的结果：
function sumFrom(a, b)
{
if (a == b)
{
return a;
}
else
{
return b + sumFrom(a, b-1);
}
}
console.log(sumFrom(1, 3)); // 6
console.log(sumFrom(2, 5)); // 14
练习的内容是，将 sumFrom 函数修改为 CPS 形式，补充 sumFromCPS 函数空白处的代码，让程序可以满足测试用例中的输出结果：
function sumFromCPS(a, b, k)
{
// ____
}
sumFromCPS(1, 3, x => console.log(x)); // 6
sumFromCPS(2, 5, x => console.log(x)); // 14
我们已经体验了手动将递归程序转变为 CPS 形式的过程，实际上存在能将代码自动转变为 CPS 形式的方法，也就是传说中 “王垠 40 行代码” 在干的事情。可以参考这两个链接查看更多内容：
因为 “自动 CPS 变换” 的难度比较大，我自己不打算学习和实现这个。