这段 javascript 代码没有看明白，请明白的人给我讲解下，非常感谢！

[palmers]

代码如下:

//Here's the standard naive factorial:

function fact(n) {
  if (n == 0)
    return 1 ;
  else
    return n * fact(n-1) ;
}
//上面这段是没有问题的，下面的看不懂,请大家讲解下，非常感谢!

//Here it is in CPS:

function fact(n,ret) {
  if (n == 0)
    ret(1) ;
  else
    fact(n-1, function (t0) {
     ret(n * t0) }) ;
}

原文在这里http://matt.might.net/articles/by-example-continuation-passing-style/

[zztao]

这是把函数当参数传入，好像是现在流行的函数式编程

[wuyuchenshishabi]

@zztao 只这样没错。，你是黄子韬？

[zztao]

原文后面给的那个直接传入一个匿名函数就比较直观看懂，这一个 ret 是一个函数

[malaohu]

递归调用。

[FrankFang128]

尾递归？

[azh7138m]

> 如果算法本身是非尾递归的，那么， CPS 变换可以将算法改写成尾调用形式，从而可以进行尾调用优化。

[bramblex]

首先，我先这篇文章前面东西都懂了，到这个 fact 这里卡住了。

fact (n, ret) 这个函数，里面的 fact(n-1, function (t0) {ret(n * t0) }) 这段代码的作用是递归构建 continuation 而已。

楼上的一众基础真差，包括某所谓的 “阿里前端”

[bramblex]

@azh7138m

哎 /w\ 这个是不能尾递归的。因为她的函数栈是没有办法优化掉的。我写了一篇专门讲尾递归的文章～

在这里～ http://lovearia.me/article/show/9

[loading]

博大精深
@bramblex

[bramblex]

@loading 我没说明白…首先，我假设楼主前面的都懂了…卡在 fact 上面了…

输入法的锅我不背

[chiu]

首先，我只是 JS 新手，仅从新手角度看这段代码。
LZ 理解第一段，说明 LZ 理解递归是怎么一回事。
然后下面的所谓 CPS 代码，用原文代码下面的例子来说：
fact()的第一个参数 n 传入 5 ，第二个 ret 传入匿名函数 function(n) {console.log(n)};
第一躺走 n==5 ，走 else ， n 变成 n-1 ，即 4 ， ret 变成 function(t0) {console.loh(n * t0)};
在这第一躺中， ret()传入 n*t0 ，并直接通过 console 输出。但这里我们并不知道 t0 是多少，所以需要递归调用 fact()进入到下一趟里，我们就能看到第一躺里的 t0 其实就是第二趟最后传入 ret()的参数((n-1)*t0)。这时第二趟的 t0 又不知道是多少，所以又进入下一趟，直到递归调用 fact()传入的 n==0 ， ret()传入 1 ，这个 1 就是上一躺需要的 t0 ，所以最后第一躺 ret()输入的参数是 5*4*3*2*1*1 。

然后，我不是很理解这种 CPS 写法的意义是什么？望指导。

[bramblex]

@chiu 在 J's 中基本上只在处理异步上意义比较大

[veficos]

@chiu CPS 的意义在于提取递归过程中函数栈的变量

[Gem]

ret 这个怎么理解？是什么意思？

[welefen]

尾递归优化

[XiXiLocked]

ret 是一个回调函数 /continuation, 意义是用当前参数算完 fact ，拿返回值接下来做什么
可以人工运行几遍，或者证明"递归 0 次 ret 是上面的意义，递归 1 次 ret 是上面的意义，。。。递归 n 次..."，记得用数学归纳法 注意每次递归 ret 都是一个新函数和前面的不一样。
举个例子
fact(2, console.log)//算出 fact(2),打印出来 #2
fact(1, function(n_2){ console.log(n_2*2);}) //算出 fact(1),送给匿名函数 #1
fact(0, function(n_1){ function(n_2){ console.log(n_2*2);}(n_1*1)}) //算出 fact(0),送给另一个匿名函数 #0
function(n_1){ function(n_2){ console.log(n_2*2);}(n_1*1)}(1)//对应于#0 的调用 1=fact(0)
function(n_2){ console.log(n_2*2);}(1*1)//对应于#1 的调用 1*1=fact(1)
console.log(2) )//对应于#2 的调用 2=fact(2)

[bramblex]

我花点时间完整讲一下吧。

如前面所说， fact (n, ret) 函数中的

// fact (n-1, function(t0) {
// ret(n*t0)
// })

就是在构建一个新的 continuation 的过程， 并把原来的再包进去。只要分步把这个函数的 continuation 一步一步展开，那就明白了。

举个🌰，展开 fact (3, ret) ，
首先 fact (3, ret) 展开成 fact (2, function(t0){ ret(3 * t0) })
知道作者为什么设一个 t0 吗？因为还有 t1, t2, t3 ，天生骄傲。（本人 t1 锤粉转黑）
然后 fact (2, ...) 展开成 fact (1, function(t1){ (function(t0){ret(3*t0})(2*t1) })
再然后 fact (1, ...) => fact(0, function(t2){ ( function(t1){ (function(t0){ret(3*t0})(2*t1) })(1*t2) })
最后 fact(0, ...) => (function(t2){(function(t1){ (function(t0){ret(3*t0})(2*t1) })(1*t2) })(1)

代入所有参数得到 ret(3*2*1*1) 就是结果（马德绕了那么一大圈）

其实段代码看似 “尾递归优化” ，但是其实跟尾递归优化一点关系都没有，而且前面所说的能优化函数栈也是扯蛋，这只是把 fact 函数调用时候的函数栈转嫁到了 continaution 上了罢了，一点都没有优化。不信我们把这个所谓 “尾递归优化” 的代码转成循环给你们看看结果。转换成循环的方式在我博客里面有 http://lovearia.me/article/show/9

// function fact(arg_n, arg_ret) {
// let n = arg_n;
// let ret = arg_ret;
//
// while (true){
// if (n == 0){
// ret(1);
// break;
// }
// else{
// let _n = n;
// let _ret = ret;
// n = _n - 1;
// ret = function(t0){_ret(_n*t0)}; // <= 会在这里爆栈，根本没有任何优化效果
// continue;
// }
// }
// }

至于前面有人提到 cps 执行的过程中可以优化函数栈，但是这时候为了递归优化而写成 cps 形式其实是很没有意义的，因为它实质就是尾递归优化，并且还需要很庞大的空间消耗来构建这个 continuation ，这和直接递归几乎没差别。这个 cps 递归只有在类似 haskell 这类惰性求值的语言中才能很好的优化，但是问题是在 haskell 这类惰性求值的语言中根本这种利用 cps 递归的写法本身又没有意义…

[SuperMild]

其实楼主那个链接里说得很清楚，这的确不是尾递归，链接里同时给出了尾递归的写法。

这个就是 CPS ，基本上就是硬生生多套了一层函数形成 callback 的形式，在 javascript 这样写的作用是避免 blocking ，把原来想直接执行的内容塞进函数里扔去执行，根据 js 天生异步的特点，就不会卡死了。

[palmers]

@XiXiLocked 谢谢 您的讲解听清楚的 非常感谢!

[palmers]

@bramblex 非常感谢! 我 刚接触 js 没多久, 非常感谢对我这个小白的指导, 谢谢 谢谢!~

[bramblex]

@palmers

这个已经不是 js 里面的内容，而属于 “程序语言理论” （ PLT ）范畴。虽然不是什么很复杂的东西，但是一般研究程序语言比较深入的人才会接触到。

然而你刚接触 js 没多久就接触到了这些东西，也确实很强啊。

[fourstring]

@bramblex 您好，看了一下您讲解尾递归的那篇文章，有几个问题想问
首先是您最开始举的那个普通递归的例子：
const fact = (n) => {
if (n <= 0) {
return 1;
} else {
return n * fact (n - 1);
}
};
它也在最后一个 return 调用了自己本身，为什么这就不是尾递归呢？
其次，您使用的“入口环境”是什么意思呢？（没太看明白）
另外，能否讲解一下进行尾递归时函数栈中的情况？（类似于您文章中“函数栈的作用”一节)
谢谢！

[fourstring]

@bramblex 刚刚去翻了翻维基百科，好像明白了。。。
非常感谢您的文章！

[bramblex]

@fourstring

[bramblex]

@fourstrin

n * fact (n - 1) 这个并不是调用自身呀，假设把乘号看成一个函数 mul 那么就得到 mul(n, fact(n-1))，并不是自身嘛

[palmers]

@bramblex 谢谢 您抬举我了

[fourstring]

@bramblex 喔，原来是这样理解，谢谢！

[markx]

请问各位能不能解释一下最后一行不能尾递归优化？ 最后一行相当于是 fact(n-1, cb); 嘛

[markx]

@markx 检查了好多遍，却还是打错了……
请问各位能不能解释一下为什么最后一行代码不能尾递归优化？ 最后一行相当于是 fact(n-1, cb); 嘛

[palmers]

@markx 因为最后一行 依然形成了串行 表达式（我自己发明的词语） 函数执行完毕后形成的算术表达式是这个样子的：

`5 * 4 * 3 * 2 * t0 ; 5 * 4 * 3 * 2 *1 * 1` //这是最后两次执行的过程

我的理解是这样的， 不知道对不对， 请参考.