代码如下:
//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/
1
zztao 2016-06-08 10:57:57 +08:00 via Android
这是把函数当参数传入,好像是现在流行的函数式编程
|
2
wuyuchenshishabi 2016-06-08 11:03:55 +08:00
@zztao 只这样没错。,你是黄子韬?
|
3
zztao 2016-06-08 11:07:21 +08:00 via Android
原文后面给的那个直接传入一个匿名函数就比较直观看懂,这一个 ret 是一个函数
|
4
malaohu 2016-06-08 11:50:56 +08:00
递归调用。
|
5
FrankFang128 2016-06-08 12:06:40 +08:00 via Android
尾递归?
|
6
azh7138m 2016-06-08 12:13:02 +08:00
> 如果算法本身是非尾递归的,那么, CPS 变换可以将算法改写成尾调用形式,从而可以进行尾调用优化。
|
7
bramblex 2016-06-08 12:18:50 +08:00
首先,我先这篇文章前面东西都懂了,到这个 fact 这里卡住了。
fact (n, ret) 这个函数,里面的 fact(n-1, function (t0) {ret(n * t0) }) 这段代码的作用是递归构建 continuation 而已。 楼上的一众基础真差,包括某所谓的 “阿里前端” |
8
bramblex 2016-06-08 12:21:10 +08:00
|
10
bramblex 2016-06-08 12:31:54 +08:00 via Android
|
11
chiu 2016-06-08 12:33:22 +08:00
首先,我只是 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 写法的意义是什么?望指导。 |
14
Gem 2016-06-08 12:38:23 +08:00
ret 这个怎么理解?是什么意思?
|
15
welefen 2016-06-08 16:01:56 +08:00
尾递归优化
|
16
XiXiLocked 2016-06-08 17:51:10 +08:00
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) |
17
bramblex 2016-06-08 17:54:27 +08:00
我花点时间完整讲一下吧。
如前面所说, 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 递归的写法本身又没有意义… |
18
SuperMild 2016-06-08 18:46:37 +08:00 via iPad
其实楼主那个链接里说得很清楚,这的确不是尾递归,链接里同时给出了尾递归的写法。
这个就是 CPS ,基本上就是硬生生多套了一层函数形成 callback 的形式,在 javascript 这样写的作用是避免 blocking ,把原来想直接执行的内容塞进函数里扔去执行,根据 js 天生异步的特点,就不会卡死了。 |
19
palmers OP @XiXiLocked 谢谢 您的讲解听清楚的 非常感谢!
|
21
bramblex 2016-06-09 00:45:47 +08:00
@palmers
这个已经不是 js 里面的内容,而属于 “程序语言理论” ( PLT )范畴。虽然不是什么很复杂的东西,但是一般研究程序语言比较深入的人才会接触到。 然而你刚接触 js 没多久就接触到了这些东西,也确实很强啊。 |
22
fourstring 2016-06-09 07:04:43 +08:00
@bramblex 您好,看了一下您讲解尾递归的那篇文章,有几个问题想问
首先是您最开始举的那个普通递归的例子: const fact = (n) => { if (n <= 0) { return 1; } else { return n * fact (n - 1); } }; 它也在最后一个 return 调用了自己本身,为什么这就不是尾递归呢? 其次,您使用的“入口环境”是什么意思呢?(没太看明白) 另外,能否讲解一下进行尾递归时函数栈中的情况?(类似于您文章中“函数栈的作用”一节) 谢谢! |
23
fourstring 2016-06-09 07:13:15 +08:00
@bramblex 刚刚去翻了翻维基百科,好像明白了。。。
非常感谢您的文章! |
24
bramblex 2016-06-09 09:31:15 +08:00 via Android
|
25
bramblex 2016-06-09 09:35:12 +08:00 via Android
|
27
fourstring 2016-06-09 22:02:34 +08:00
@bramblex 喔,原来是这样理解,谢谢!
|
28
markx 2016-06-12 09:48:42 +08:00
请问各位能不能解释一下最后一行不能尾递归优化? 最后一行相当于是 fact(n-1, cb); 嘛
|