// 不尾递归 function f(n) { if (n === 0 || n === 1) return n else return f(n - 1) + f(n - 2) } // 尾递归
二、尾调用优化 尾调用之所以与其他调用不同,就在于它的特殊的调用位置。 我们知道,函数调用会在内存形成一个"调用记录",又称"调用帧"(call frame),保存调用位置和内部变量等信息。...这就叫做"尾调用优化"(Tail call optimization),即只保留内层函数的调用记录。如果所有函数都是尾调用,那么完全可以做到每次执行时,调用记录只有一项,这将大大节省内存。...这就是"尾调用优化"的意义。 三、尾递归 函数调用自身,称为递归。如果尾调用自身,就称为尾递归。...对于其他支持"尾调用优化"的语言(比如Lua,ES6),只需要知道循环可以用递归代替,而一旦使用递归,就最好使用尾递归。...arguments:返回调用时函数的参数。 func.caller:返回调用当前函数的那个函数。 尾调用优化发生时,函数的调用栈会改写,因此上面两个变量就会失真。
需要了解如何优化尾递归的话,我们需要从最开始讲起。 什么是尾调用 什么是尾递归 如何优化尾递归 尾调用 从字面理解,自然而言就是在函数的尾部返回一个函数的调用,通常来说,指的是函数执行的最后一步。...如果递归链过长,可能会stack overflow 那么我们是不是可以做优化呢,这就可以涉及上面提到的尾调用,它的原理是啥呢?...因为尾调用时函数的最后一部操作,所以不再需要保留外层的调用帧,而是直接取代外层的调用帧,所以可以起到一个优化的作用。...手动优化 既然我们知道了,很多浏览器对于尾递归的优化支持的浏览器并不多,那你会好奇,当我们使用尾递归进行优化的时候,依然出现栈溢出的错误,那么我们如何解决呢??...对于尾递归而言,我们需要了解优化它的原理,如果有必要的话,将递归的形式写成迭代的形式,通过迭代方式,降低重复值的计算,当然了,这个过程,有时候是比较难的,值得我们去思考。 参考 尾调用和尾递归
之前分享过递归,其中有一个优化就是尾调用。 先明确尾调用的概念: 尾调用(Tail Call)是函数式编程的一个重要概念,就是指某个函数的最后一步是return调用另一个函数。...注意,并不是所有的函数都能尾调用优化,要看你这个函数需不需要使用某些上个函数的变量或者什么的。...尾调用优化其实很大一部分就是递归函数在使用,因为递归函数调用的时候非常耗费内存,可能需要保存成百上千调用栈,很容易内存溢出。如果是尾递归就只有一个调用栈,能把复杂度O(n)的变成O(1)。...Function) { f = f(); } return f; } 执行: trampoline(sum(1, 100000)) 你会发现,很多递归函数都能改成类似的,然后使用蹦床函数实现尾调用优化...而ES6对尾调用有什么优化?就是函数默认值,在一些场景下,比如阶乘的递归,采用默认值实现尾递归优化。 (完)
Photo by Benni Asal on Unsplash 尾调用 啥是尾调用? 尾调用就是函数的最后一个步骤调用另一个函数 比方说: ?...20190307171547.png 函数在调用的时候会在调用栈中 push 一个调用帧,每次执行完函数都会逐一弹出调用帧知道所有函数执行完毕,调用栈被清空: 调用栈中的同步代码 1function f1...首先执行 script ,将 main 主程序推入调用栈中并执行,发现需要调用 f3 将 f3 函数推入调用栈中,执行 f3,发现需要调用 f2 将 f2 函数推入调用栈中,执行 f2, 发现需要调用...最后将 console.log 弹出调用栈,代码执行完毕 尾调用优化 每次在函数被调用的时候,内存都会保存调用帧。...尾调用因为是函数的最后一步,因此并不需要外层函数的调用帧。我们只需要将最后需要执行另外一个函数之前用 return 操作符显式表明"不再需要此函数"即可 ?
调用栈的英文名叫做Call Stack,大家或多或少是有听过的,但是对于js调用栈的工作方式以及如何在工作中利用这一特性,大部分人可能没有进行过更深入的研究,这块内容可以说对我们前端来说就是所谓的基础知识...针对这种情况除了我们要尽量避免函数层级嵌套的比较深之外,ES6提供了“尾调用优化”来解决调用侦过多,引起的内存消耗过大的问题。 何谓尾调用: 尾调用指的是:函数的最后一步是调用另一个函数。...// return undefined; // 隐式的return } 尾调用优化优化了什么?...} 尾调用优化只在严格模式下开启,非严格模式是无效的。...如果环境不支持“尾调用优化”,代码还可以正常运行,是无害的!
针对这种情况除了我们要尽量避免函数层级嵌套的比较深之外,ES6提供了“尾调用优化”来解决调用侦过多,引起的内存消耗过大的问题。 何谓尾调用: 尾调用指的是:函数的最后一步是调用另一个函数。...// return undefined; // 隐式的return } 尾调用优化优化了什么?...现在可以使用“尾调用优化”来写一个“尾递归”,只保存一个调用侦,来防止爆栈问题。 注意: 只有不再用到外层函数的内部变量,内层函数的调用帧才会取代外层函数的调用帧。...} 尾调用优化只在严格模式下开启,非严格模式是无效的。...如果环境不支持“尾调用优化”,代码还可以正常运行,是无害的!
而尾递归之所以可以优化,是因为每次递归调用的时候,当前作用域中的局部变量都没有用了,不需要层层增加调用栈再在最后层层回收,当前的调用帧可以直接丢弃了,这才是尾调用可以优化的原因。...由于尾递归是尾调用的一种特殊形式,相对简单一些,在 ES6 没有开启尾调用优化的时候,我们可以手动为尾递归做一些优化。...尾递归优化 改写为循环 之所以需要优化,是因为调用栈过多,那么只要避免了函数内部的递归调用就可以解决掉这个问题,其中一个方法是用循环代替递归。...原因是在他们看来,尾调用优化仍然存在一些问题,主要有两点: 难以辨别 在引擎层面消除尾递归是一个隐式行为,函数是不是符合尾调用的要求,可能程序员在写代码的时候不会意识到,另外由于开启了尾调用优化,一旦出现了死循环尾递归...语句中的尾调用 在 JS 语句中,以下几种情况可能包含尾调用: + 代码块中(由 {} 分隔的语句) + if 语句的 then 或 else 块中 + do-while,while,for 循环的循环体中
尾调用优化 尾调用之所以与其他调用不同,就在于其特殊的调用位置。 我们知道,函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。...这就叫作”尾调用优化“(Tail Call Optimization),即只保留内层函数的调用帧。如果所有函数都是尾调用,那么完全可以做到每次执行时调用帧只有一项,浙江大大节省内存。...这就是”尾调用优化“的意义。...对于其他支持”尾调用优化“的语言(比如 Lua、ES6),只需要知道循环可以用递归代替,而一旦使用递归,就最好使用尾递归。 严格模式 ES6 的尾调用优化只在严格模式下开启,正常模式下是无效的。...回答是肯定的——自己实现尾递归优化。 原理非常简单。尾递归之所以需要优化,愿意是调用栈太多造成溢出,那么只要减少调用栈就不会溢出了。怎么做可以减少调用栈呢?答案是采用”循环“替换”递归“。
在尾调用优化中,这些属性不再有用,因为相关的信息可能以及被移除了。...因此,严格模式(strict mode)禁止这些属性,并且尾调用优化只在严格模式下有效。 如果尾调用优化生效,流程图就会变成这样: ?...这就叫做尾调用优化,如果所有的函数都是尾调用的话,那么在调用栈中的调用帧始终只有一条,这样会节省很大一部分的内存,这也是尾调用优化的意义。 尾递归 1....// Safari浏览器进行了尾调用优化,factorial(500000, 1)结果为Infinity,因为结果超出了JS可表示的数字范围 // 如果在node v6版本下执行,需要加--harmony_tailcalls...要注意的是,经过测试,Chrome和Firefox并没有对尾调用进行优化,Safari对尾调用进行了优化。 Node高版本也已经去除了通过--harmony_tailcalls参数启用尾调用优化。
,并没有 return 该调用,所以JS引擎会认为你还没有执行完,会保留你的调用帧。...在尾调用优化中,这些属性不再有用,因为相关的信息可能以及被移除了。...这就叫做尾调用优化,如果所有的函数都是尾调用的话,那么在调用栈中的调用帧始终只有一条,这样会节省很大一部分的内存,这也是尾调用优化的意义。 尾递归 1....// Safari浏览器进行了尾调用优化,factorial(500000, 1)结果为Infinity,因为结果超出了JS可表示的数字范围 // 如果在node v6版本下执行,需要加--harmony_tailcalls...要注意的是,经过测试,Chrome和Firefox并没有对尾调用进行优化,Safari对尾调用进行了优化。 Node高版本也已经去除了通过--harmony_tailcalls参数启用尾调用优化。
什么是尾调用优化?...对于尾调用优化,因此必须找出表达式中函数调用的尾部。只有下列表达式会包含尾调用: 条件操作符 (?...其他此类声明语句都有无法被优化的上下文。如下所示,当expr部分包含尾调用时,下列声明语句就包含尾调用。...bar()做了尾调用优化,那么其返回值就有可能改变了foo的行为。...3.1 尾递归循环 尾调用优化使得在递归循环中不增长调用栈成为可能。下面举两个例子。
总括: 本文介绍了尾调用,尾递归的概念,结合实例解释了什么是尾调用优化,并阐述了尾调用优化如今的现状。...这就是尾调用优化的意义。 但尾调用优化仅仅是普通开发者去写可以被优化的函数是做不到的,这个特性一般都需要借助编译器或是运行环境来支持才可以。...Javascript原来是不支持尾递归调用优化的,ES6中才开始规定程序引擎应在严格模式下使用尾调用优化。而且ECMAScript 6限定了尾位置不含闭包的尾调用才能进行优化。...尾调用优化默认关闭 看到这想必一定很好奇,既然尾调用优化如此高效,为何都默认关闭了这个特性呢?答案分为两方面: 隐式优化问题。...Chrome下使用尾递归写法的方法依旧出现调用栈溢出的原因在于: 直接原因: 各大浏览器(除了safari)根本就没部署尾调用优化; 根本原因: 尾调用优化依旧有隐式优化和调用栈丢失的问题; 既然尾调用优化是默认关闭的
优化在哪里在执行到outer中的return语句的时候,要先计算inner函数的值。这时候JS引擎发现,把第二个栈帧弹出去也没有关系。...这就是ES6尾调用优化的关键递归优化的条件代码在严格模式下执行外部函数的返回值,是对尾调用函数的调用尾调用函数返回后,不需要执行额外的逻辑尾调用函数不是外部函数作用域中自由变量的闭包下面是《高程》里面的示例...,帮助大家理解// 无优化: 尾调用没有返回function outer(){ inner();}// 无优化: 尾调用没有直接返回function outer(){ let innerResult...();}其实我觉得上面的倒数第二个,它是完全可以尾调用优化的。...相信你会和我一样,会不由自主的感叹总结JS中的递归函数调用的时候,上下文栈是怎么变化的什么是递归优化递归优化的条件是什么手动优化一个递归代码
尾递归和尾递归优化 之前提到过尾调用,尾调用就是函数的最后一步调用另外一个函数。那么递归就是调用自身,尾递归就是再函数的最后一步调用自身。?...在计算机学里,尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形,即最后一步新调用的返回值直接被当前函数的返回结果。此时,该尾部调用位置被称为尾位置。...尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理,尾递归形式的函数的运行效率可以被极大地优化。...---wikipedia 和尾调用一样,尾递归因为调用栈中只存在一个调用记录,因此不会像普通递归那样耗费那么多内存。...} 默认大部分浏览器不会对尾递归进行优化 如果需要尝试可以安装 node 6.5 - 7 之间的版本测试;开启 node 需要增加 flag --harmony-tailcalls --use-strict
因为函数调用的过程,都要借助“栈”这种存储结构来保存运行时的一些状态,比如函数调用过程中的变量拷贝,函数调用的地址等等。...从“尾”字可看出来即若函数在尾巴的地方递归调用自己。...尾递归优化 当你给编译选项开了优化之后,见证奇迹的时刻到了,居然能算出正确结果。如图所示: ? C++ 默认 segmentation fault, 开启编译优化后,能正常计算结果。...默认启用尾递归优化正常计算结果,禁用尾递归优化则“StackOverflow”。 我们来看看生成的字节码有什么不同。 ? 包含尾递归优化的字节码,直接 goto 循环。 ?...禁用尾递归优化的字节码,方法调用。 从上面可以看出,尾递归优化后,变成循环了(前面的 C++ 类似)。 好了,尾递归咱们就了解到这里。
python尾递归优化如何实现 说明 1、尾递归是指在函数返回时调用自身,return语句不能包含表达式。...2、通过这种方式,编译器或解释器可以对尾递归进行优化,从而使递归本身仅占用一个栈帧,而不会发生栈溢出。...product): if num == 1: return product return fact_iter(num - 1, num * product) 以上就是python尾递归优化的实现
优化在哪里 在执行到outer中的return语句的时候,要先计算inner函数的值。这时候JS引擎发现,把第二个栈帧弹出去也没有关系。...这就是ES6尾调用优化的关键 递归优化的条件 代码在严格模式下执行 外部函数的返回值,是对尾调用函数的调用 尾调用函数返回后,不需要执行额外的逻辑 尾调用函数不是外部函数作用域中自由变量的闭包 下面是《...高程》里面的示例,帮助大家理解 // 无优化: 尾调用没有返回 function outer(){ inner(); } // 无优化: 尾调用没有直接返回 function outer(){...foo; } return inner(); } 其实我觉得上面的倒数第二个,它是完全可以尾调用优化的。...相信你会和我一样,会不由自主的感叹 总结 JS中的递归函数调用的时候,上下文栈是怎么变化的 什么是递归优化 递归优化的条件是什么 手动优化一个递归代码
什么是尾递归? 尾递归是指,在函数返回时,调用自身本身,即return语句不能包含表达式。 尾递归与一般的递归不同在于对内存的占用:普通递归创建stack累积而后计算收缩,尾递归只会占用恒量的内存。...尾递归优化 当编译器检测到一个函数调用时尾递归时,它就覆盖当前的活动记录,而不是在栈中去创建一个新的,这样所使用的栈空间就大大缩减,使得实际的运行效率变得更高,这个过程也叫编译器把尾递归做优化。...python编译器没有尾递归优化的功能,递归深度超过1000时会报错,因此需要我们通过实现一个tail__call__optimized装饰器来优化尾递归: # Python3的装饰器 import sys...: 当递归函数被该装饰器修饰后,递归调用在装饰器while循环内部进行,每当产生新的递归调用栈时,就捕获当前尾调用函数的参数,并抛出异常,从而销毁递归栈并使用捕获的参数手动调用递归函数。...参考资料: (24条消息) Python尾递归_BrownWong的博客-CSDN博客_python 尾递归 Python当中的尾递归优化 - 知乎 (zhihu.com) Python中的尾递归 -
就当我觉得可以轻而易举解决问题的时候,突然发现 test 函数定义就没有参数,调用的时候也没传参数,真是太诡异了。...: in function [C]: in function 'xpcall' init_worker_by_lua:52: in function 看到这里,估计有人已经猜到原因了:问题似乎和尾调用...init_worker_by_lua:45: in function [C]: in function 'xpcall' init_worker_by_lua:52: in function 当我们去掉尾调用后...,错误信息恢复了正常,验证了我们的猜测,诡异错误信息确实和尾调用相关。...当然,真正的问题是因为我们在使用 cjson.decode 的时候传递了错误的参数,尾调用本身并没有问题,但是不得不说的是,它拐带的错误信息实在是坑人。
领取专属 10元无门槛券
手把手带您无忧上云