大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说JS-图解尾递归优化-秒懂「终于解决」,希望您对编程的造诣更进一步.
JS中的递归
我们来看一个阶乘的代码
function foo( n ){
if(n <= 1){
return 1;
}
return n * foo( n - 1 );
}
foo(5); // 120
下面分析一下，代码运行过程中,执行上下文栈是怎么变化的
- 这个代码是在全局作用域中执行的，所以在foo函数得到执行之前，上下文栈中就已经被放入了一个全局上下文。之后执行一个函数，生成一个新的执行上下文时，JS引擎都会将新的上下文push到该栈中。如果函数执行完成，JS引擎会将对应的上下文从上下文栈中弹出
- 一开始执行foo函数的时候，JS引擎会创建foo的执行上下文，将该执行上下文push进上下文栈。然后开始执行foo中的代码。
现在上下文栈中已经有了两个执行上下文了
- 在执行到foo中代码快结束时，return表达式中，又调用了foo函数。所以又会创建一个新的执行上下文。并且JS引擎会把这新的执行上下文push到上下文栈中。
现在上下文栈中已经有了三个执行上下文了
- 开始重复第3步的执行。一直到n<=1，才不会有新的执行上下文产生。
此刻上下文栈中，已经有了6个上下文了（包含了全局上下文）
设想一下
- 如果刚开始调用的时候，传入n的初始值为100，到n<=1时，上下文栈中会有几个上下文。101个。
- 如果初始值为1000呢？到n<=1时，会有1001个执行上下文
- 也就是说，传入的初始值越大，执行上下文栈中，就会有越多的执行上下文🥲
- 对于上下栈，它的空间是有限的，一旦存放的上下文占用内存产出了它的最大内存，就会出现栈溢出。
RangeError: Maximum call stack size exceeded - 而在chrome中，不仅会对栈的空间有限制，还会对函数的递归次数有限制
递归优化
我们来看一个样例代码
function outer() {
return inner();
}
outer();
分析一下，这里的上下文栈是怎么变化的
- 调用outer函数的时候，第二个栈帧被推到了栈上。
第一个栈帧是全局上下文
把上下文栈中的一个上下文称作一个栈帧
- 执行到了return语句，必须要计算inner调用结果，才能返回值
- 调用inner函数，第三个栈帧被推入到栈上。
- 执行inner函数，将返回值传回到outer函数。inner执行完毕。第三个栈帧被弹出栈
- outer函数再返回值。outer函数执行完毕，第二个栈帧被弹出栈
等等，情况不是一样的么？优化在哪里
- 在执行到outer中的return语句的时候，要先计算inner函数的值。这时候JS引擎发现，把第二个栈帧弹出去也没有关系。因为到时候，直接拿inner的返回值返回出去就好了，第二个栈帧就没有必要保存了。
- 将第二个栈帧弹出
这个时候，栈中只有一个栈帧了–全局上下文
- 执行到inner函数，inner函数的上下文被push到栈中
这个时候，栈中有两个栈帧了
- 开始执行inner函数，计算返回值后，inner函数执行完毕。inner的上下文栈帧被弹出栈。
栈中又只剩一个栈帧了–全局上下文
综上，我们可以看出：如果没有优化，没多调用一次嵌套函数，就会多增加一个栈帧；有了优化之后，无论调用多少次嵌套，栈中只会有两个栈帧。这就是ES6尾调用优化的关键😄
这是理想情况，实际情况没有这么美好
尾递归优化是调用栈的优化，并不是完全没有多个栈帧。而是用了尾递归的写法之后，代码运行所递归的次数会变得更多。并且，在相同的递归次数情况下，尾递归写法的运行时间也会少些
举个例子：没有用尾递归的写法，递归1000次导致栈溢出；用了尾递归写法，递归2000次才导致栈溢出。（数字是虚构的，具体多少据环境而定）
递归优化的条件
- 代码在严格模式下执行
- 外部函数的返回值，是对尾调用函数的调用
- 尾调用函数返回后，不需要执行额外的逻辑
- 尾调用函数不是外部函数作用域中自由变量的闭包
下面是《高程》里面的示例，帮助大家理解
// 无优化： 尾调用没有返回
function outer(){
inner();
}
// 无优化： 尾调用没有直接返回
function outer(){
let innerResult = inner();
return innerResult;
}
//无优化： 尾调用返回值后，必须要转型为字符串
function outer(){
return inner().toString();
}
// 无优化： 尾调用是一个闭包
function outer(){
let foo = 'bar';
function inner(){ return foo; }
return inner();
}
其实我觉得上面的倒数第二个，它是完全可以尾调用优化的。因为这个计算是不需要外部函数的上下文里面内容支持的。可能是这样的计算必须要在外部函数的上下文中完成吧，咱也不懂。记一下吧。
有哪位同仁能够帮我解答一下我这个问题吗😁
实操一个优化代码
下面是一个普通的求斐波那契数列的函数
function fib( n ){
if( n < 2){
return n;
}
return fib(n - 1) + fib(n - 2)
}
这是一个非常简单的斐波那契数列的函数，可以看到它不符合尾递归的条件。因为返回值的调用函数参与了额外计算
我们来优化一下
function fib( n ){
return fibImpl(0, 1, n);
}
function fibImpl(a, b, n){
if(n === 0){
return a;
}
return fibImpl(b, a+b, n-1);
}
看，这样是不是就符合尾递归调用函数了
简单讲解一下上面的代码
- 把原先的一个函数拆成了两个
- 第一个函数接受一个参数。这个参数表示求第几位的斐波那契数。
- 第二个参数接收三个参数。前两个参数表示正在计算的两个位置的数字，第三个参数表示还要计算多少次
斐波那契数规律，就是从第三位开始，每一位的数字都是前两位数字的和
那上面的计算的阶乘代码怎么优化呢？
function foo( n ){
if(n <= 1){
return 1;
}
return n * foo( n - 1 );
}
foo(5); // 120
这个是上面计算阶乘的代码，我们可以用同样的思路，来对其做尾递归函数优化
function foo( n ){
return inner(n, n - 1)
}
function inner(sum, n){
if(n <= 1){
return sum；
}
return inner(sum * n , n -1);
}
foo(5);
是不是超简单😁
最新版的浏览器已经支持尾递归
可以在计算斐波那契数列的时候，比较尾递归和非尾递归的时间。相信你会和我一样，会不由自主的感叹
总结
- JS中的递归函数调用的时候，上下文栈是怎么变化的
- 什么是递归优化
- 递归优化的条件是什么
- 手动优化一个递归代码
- 如果有哪里你看不明白的地方，一定要告诉我，谢谢🙏
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/13504.html
