Babel 编译 ES6 生成 ES5尾递归的做法我还是不明白, 用 Object 方法可以绕过调用栈吗?
好文章,就是前面提及复杂度的时候,应该表明是空间复杂度,而非时间复杂度。
刚开始学Lisp,自己也这么用,只是不知道概念。阮老师写得简单明了。
请教一下阮老师,在柯里化的范例中,使用 call 的用意为何呢?
尝试将原本 return fn.call(this, m, n); 改成 return fn(m, n);,发现亦能正常运作
我臆测了一下,猜想会不会透过使用 call function,能使 currying 函数的複用性较强呢?
麻烦老师指点迷津了!
所以说 ES6 才有这种优化吗?
ES5 递归时写尾调用有效果吗 ?
惭愧,第一次了解到存在尾调用优化方法。经查c++同样支持这种优化,收益良多。感谢。
引用桑凯的发言:请教一下阮老师,在柯里化的范例中,使用 call 的用意为何呢?
尝试将原本 return fn.call(this, m, n); 改成 return fn(m, n);,发现亦能正常运作
我臆测了一下,猜想会不会透过使用 call function,能使 currying 函数的複用性较强呢?
麻烦老师指点迷津了!
是绑定this用的,也就是作用域,或者目标。 你搜下call函数的文档就明白啦
豁然开朗啊
学习了,对于这个尾调用以前了解没这么深刻。现在感觉很不错,感觉自己又进步了。
和yacc或bison写语法规则一样,需要避免右递归,尽可能使用左递归,是一个意思。赞阮老师
所以说 ES6 才有这种优化吗?
ES5 递归时写尾调用有效果吗 ?
不知Python有没有对尾调用,尾递归做规定?
希望也能优化下例:
function fn(x){
let a=1, b=2;
fn2(1, x);
return;
}
大师,这个尾递归还是会溢出啊。。Uncaught RangeError: Maximum call stack size exceeded
function factorial(n) {
if (n===1) return 1;
return n * factorial(n - 1);
}
factorial(50000) // 120
引用oceanstick的发言:大师,这个尾递归还是会溢出啊。。Uncaught RangeError: Maximum call stack size exceeded
function factorial(n) {
if (n===1) return 1;
return n * factorial(n - 1);
}factorial(50000) // 120
这种都不是尾递归啊,你没仔细看文章。
----------------------------------------------------
function factorial(n, total) {
if (n===1) return total;
return factorial(n - 1, n * total);
}
factorial(50000, 1)
改成这样才是尾递归
阮老师 Tail Call Optimization 就是说,在 ES6 中,只要使用尾递归,就不会发生栈溢出,相对节省内存,这句话是不是不够谨慎? 因为在es6 也只有在严格模式下会有Tail Call Optimization 尾调用优化 而非严格模式其实是没有尾调用优化的。
@冷无缺:
谢谢指出,改过来了。
"use strict";
function sum(x, y){
if (y > 0){
return sum(x+1, y-1);
}else{
return x;
}
}
console.log(sum(1, 100000))
阮老师,上面的代码不也是尾调用吗?为何我在babeljs下运行还是会出现栈溢出呢?
@blackcater:看caniuse,目前没有一个浏览器支持,包括Babel。
阮老师细节抓的真准啊
引用桑凯的发言:请教一下阮老师,在柯里化的范例中,使用 call 的用意为何呢?
尝试将原本 return fn.call(this, m, n); 改成 return fn(m, n);,发现亦能正常运作
我臆测了一下,猜想会不会透过使用 call function,能使 currying 函数的複用性较强呢?
麻烦老师指点迷津了!
引用笑画戈的发言:是绑定this用的,也就是作用域,或者目标。 你搜下call函数的文档就明白啦
currying 中返回的是一个方法,这个方法很有可能会被挂载到某个对象上面。所以这里需要用call去改写一下context,防止 currying过程总 context被改写。该例子中确实用不用call都没问题。
兔哥威武,很好的入门资料~
function factorial(n) {
'use strict';
var arr=new Array(10000);
if (n===1) return 1;
return 1 * factorial(n - 1);//这里不是尾调用,需要保存n个调用记录,复杂度 O(n)
}
function _factorial(n, total) {
'use strict';
var arr=new Array(10000);
if (n===1) return total;
return _factorial(n - 1, 1 * total);
}
阮老师,您好.
我有一个疑问, 请问下面的函数是尾递归调用的吗?
const fun=a=> b=> a==0 ? a : fun(b-1)(b+a)
老师好,最近在学习你的ES6入门教程。遇到关于尾递归优化的疑问:以非波数列为例
//1.普通递归
function Fibonacci0(n){
if(n
return Fibonacci0(n-1)+Fibonacci0(n-2);
}
Fibonacci0(10);//89
Fibonacci0(100);// 卡住了~~~等了很久都没看到执行结果
Fibonacci0(10000);// 同上
//2.改写为尾递归
"use strict";
function Fibonacci1(n,temp=1,result=1){
if(n
return Fibonacci1(n-1,result,temp+result);
}
console.log(Fibonacci1(100));//573147844013817200000
console.log(Fibonacci1(10000));//Infinity
console.log(Fibonacci1(1000000));//报错 RangeError: Maximum call stack size exceeded
//3.采用蹦床函数
function Fibonacci2(n,temp=1,result=1){
if(n
return Fibonacci2.bind(null,n-1,result,temp+result);
}
//console.log(Fibonacci2(100));
//console.log(Fibonacci2(1000));
//蹦床函数
function trampoline(f){
while (f&&f instanceof Function){
f=f();
}
return f;
}
console.log(trampoline(Fibonacci2(1000000)));//Infinity
想要问一下尾递归优化是否有在以上方法2,3中实现?它们之间的区别是什么?
谢谢阮老师!愿你满得智慧与聪明,生活充满平安与喜乐:)
上午发的留言好像没显示。。。
@李洋:
阶乘尾递归最多Infinity咋能溢出呢
从第一篇文章看到现在,内容越来越深入。柯里化、尾调用优化…需要的基础越来越深入了,支持你
上面代码中,如果函数g不是尾调用,函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后,函数f就结束了,所以执行到最后一步,完全可以删除 f() 的调用记录,只保留 g(3) 的调用记录
----
chrome 断点下在 g 函数中,在 call stack 还是能看到 f 的信息,无论 g 是不是尾调用.
不是很清楚 为什么 f 不是尾调用就要保存 m 和 n 的值
我测试了这个函数发现call stack里面还是记录了每次调用的记录
function factorial(n, total) {
if (n===1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
而且我是用'use strict';还是没有任何变化
为何在严格模式下使用了尾递归优化还是会出现栈溢出的错误?
严格模式下禁用的是func.arguments,不是arguments
建议修改
这里的“尾调用优化”,应该是指 PTC,而非 TCO,具体区别见:
http://www.zcfy.cc/article/all-about-recursion-ptc-tco-and-stc-in-javascript-2813.html
想请教下。你文章里写的“尾递归的实现,往往需要改写递归函数,确保最后一步只调用自身。做到这一点的方法,就是把所有用到的内部变量改写成函数的参数。”,结合文中的代码示例,是不是可以理解为:
```
function factorial(n) {
if (n===1) return 1;
return n * factorial(n - 1); // 最后一步引用了变量n,so不算尾递归。并且由于引用变量n,so需要保存n个调用记录
}
factorial(5) // 120
```
```
function factorial(n, total) {
if (n===1) return total;
return factorial(n - 1, n * total); // 由于未引用变量,so只保留一个调用记录,复杂度 O(1)
}
factorial(5, 1) // 120
```
如果我的理解有误,麻烦指正。谢谢阮大大
请问 为什么这段程序启用了了严格模式, 这样的尾递归, 在chrome浏览器里面也会溢出
// 尾递归
"use strict";
function recursion(num){
new_num=num + 1
if (num >=40000){
return
}
console.log("尾递归|第",new_num,"次调用")
return recursion(new_num)
}
recursion(1)
@昭昭:
V8引擎的尾递归优化已经默认关闭了
引用昭昭的发言:请问 为什么这段程序启用了了严格模式, 这样的尾递归, 在chrome浏览器里面也会溢出
// 尾递归
"use strict";
function recursion(num){
new_num=num + 1
if (num >=40000){
return
}
console.log("尾递归|第",new_num,"次调用")
return recursion(new_num)
}recursion(1)
目前所有瀏覽器只有 Safari 有支持 Tail Call Optimization,就連 node 因為是用 Chrome V8 也沒有支持 Tail Call Optimization
您好,在维基百科尾调用词条"定义与说明"一节 (https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8#%E7%89%B9%E5%BE%81%E4%B8%8E%E7%AE%80%E5%8D%95%E7%A4%BA%E4%BE%8B) 中提到,这样的写法中 a(data) 是位于函数的尾位置的:
function foo2(data) {
var ret=a(data);
return ret;
}
但您的文章中提到这不属于尾调用.是维基百科写错了吗?
感谢此文。
// 情况一
function f(x){
let y=g(x);
return y;
}
您引用的维基百科中,这个形式的调用属于尾调用。
只不过对于js,在中也有说明,这样的形式不被认定为可以进行尾调用优化。但是这个例子确实是一个尾调用。不是吗?
@Jamie:
文章有误 确实是一个尾调用 我在node里测试了
之前看这篇文章的时候,测试了一下 demo 代码,发现改写后的 factorial 确实要快非常多。当时没多想,以为“尾调用优化”的功劳。
今天再看,发现其实不是这样的,性能提升的根本原因其实是算法的优化。
factorial的时间复杂度是:O(2^n);
factorial2的时间复杂度是:O(n);
因此才会有这么明显的提升效果。
chrome90以上好像不支持“尾调用优化”了,之前还能不报错,现在无论怎么写只要是复杂度够高都会抛错。不过改写之后算法效率会高很多,能支持的复杂度有了提升:比如以前支持1万次嵌套,改写之后能支持到2万次,但是3万依旧会报错。
看了阮老师的文章,收获颇丰,感谢阮老师。我有几个疑问,望阮老师解答。
1 为什么说蹦床函数不是真正的尾递归优化?
2 tco函数没有处理异常,如果里面出现异常,active等状态就可能不正确。下次再调用sum会有问题。
可以改写成下面这样,并且每次都要tco一下。
var sum
function sum0(x,y){
if (y > 0) {
return sum(x + 1, y - 1)
} else {
return x
}
}
//第一次调用
sum=tco(sum0);
console.info(sum(1,3))
//第二次调用
sum=tco(sum0);
console.info(sum(1,3))
这样没问题吧?
> 上面代码中,如果函数g不是尾调用,函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后,函数f就结束了,所以执行到最后一步,完全可以删除 f() 的调用记录,只保留 g(3) 的调用记录。
这个例子是内联,而不是尾递归优化。假设f函数包含尾递归调用,优化的是f函数内部。而和f的调用者毫无关系
https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8#%E6%B1%87%E7%BC%96%E9%87%8D%E7%BB%84
https://stackoverflow.com/questions/310974/what-is-tail-call-optimization
Jogis 说:
昨天找了一下尾递归资料,看到yuan老师以前也写过一篇相关文章,还打算找一些函数式编程语言学学,没想到ES6已经支持了尾递归优化,加上Lodash,对于函数式编程来说,js已经够用了,谢谢老师及时的文章。
2015年4月10日 12:09 | # | 引用