如何优化尾调用

         

成都创新互联服务项目包括桐柏网站建设、桐柏网站制作、桐柏网页制作以及桐柏网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，桐柏网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到桐柏省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

 前言

在这里关于递归，这里就不赘述了，有兴趣的可以去查一查资料。

需要了解如何优化尾递归的话，我们需要从最开始讲起。

  • 什么是尾调用
  • 什么是尾递归
  • 如何优化尾递归

尾调用
从字面理解，自然而言就是在函数的尾部返回一个函数的调用，通常来说，指的是函数执行的最后一步。

举个例子

 
 
 
    
  
  
  
  1. const fn = () => f1() || f2() 
    2. 
  
  
  
  2. // 这里的话, f2函数有可能是尾调用,f1不可能是尾调用 
    3.

为什么f1函数不是呢，我们看这个函数的等价形式

 
 
 
    
  
  
  
  1. const fn = function () { 
    2. 
  
  
  
  2.     const flag = f1() 
    3. 
  
  
  
  3.     if(flag) { 
    4. 
  
  
  
  4.         return flag 
    5. 
  
  
  
  5.     } else { 
    6. 
  
  
  
  6.         return f2() 
    7. 
  
  
  
  7.     } 
    8. 
  
  
  
  8. } 
    9.

似乎写到这里，根据尾调用定义，我们就明白了，只有f2函数是在尾部调用。

说到这里，为什么要说尾调用呢?我们事先想一想传统的递归，典型的就是首先执行递归调用，然后根据这个递归的返回值并结算结果，那么传统的递归缺点有哪些呢

  • 效率低，占内存。
  • 如果递归链过长，可能会stack overflow

那么我们是不是可以做优化呢，这就可以涉及上面提到的尾调用，它的原理是啥呢

“按照阮一峰老师在es6的函数扩展中的解释就是：函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部还调用函数C，那就还有一个C的调用帧，以此类推。所有的调用帧，就形成一个“调用栈”（call stack）。
“这里的“调用帧”和“调用栈”，说的应该就是“执行环境”和“调用栈”。因为尾调用时函数的最后一部操作，所以不再需要保留外层的调用帧，而是直接取代外层的调用帧，所以可以起到一个优化的作用。
从上述的描述中，我们视乎可以理解成

  • 它的原理类似于当编译器检测到一个函数调用是尾递归时，它会覆盖当前的活动记录而不是在函数栈中创建一个新的调用记录。
  • 这样子，我们也可以理解成，不同的语言编译器或者是解释器做了尾递归优化，才让它不会爆栈。

既然是这样子的话，尾递归的优化，取决于浏览器，那具体有哪些主流浏览器支持呢

safari 和火狐，有兴趣的可以去了解一下，可以写个斐波那契数列数列验证一下。

手动优化
既然我们知道了，很多浏览器对于尾递归的优化支持的浏览器并不多，那你会好奇，当我们使用尾递归进行优化的时候，依然出现栈溢出的错误，那么我们如何解决呢？

我在网上看到一个不错的方案，采用的是蹦床函数

 
 
 
    
  
  
  
  1. function trampoline(f) { 
    2. 
  
  
  
  2.   while (f && f instanceof Function) { 
    3. 
  
  
  
  3.     f = f(); 
    4. 
  
  
  
  4.   } 
    5. 
  
  
  
  5.   return f; 
    6. 
  
  
  
  6. } 
    7.

那么如何使用呢

我们拿最常见的斐波那契数列来说吧

 
 
 
    
  
  
  
  1. function fibonacci(n) { 
    2. 
  
  
  
  2.   if (n === 0) return 0 
    3. 
  
  
  
  3.   if (n === 1) return 1 
    4. 
  
  
  
  4.   return fibonacci(n - 1) + fibonacci(n - 2) 
    5. 
  
  
  
  5. } 
    6.

根据上面的式子，我们可以将其写成迭代形式，用一个变量去缓存它的值

 
 
 
    
  
  
  
  1. function fibonacci (n, ac1 = 0, ac2 = 1) { 
    2. 
  
  
  
  2.     return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2); 
    3. 
  
  
  
  3. } 
    4.

其实试过的小伙伴，会发现，当你需要求的n足够大的时候，还是会报错，类似于下面的错误信息

 
 
 
    
  
  
  
  1. // fibonacci(10000) 
    2. 
  
  
  
  2. Uncaught RangeError: Maximum call stack size exceeded 
    3.

这个时候，那么我们如何去优化呢？难道真的没有办法可以解决了吗

这里得借鉴下别人的思路，我觉得挺不错的，这里就给出代码

 
 
 
    
  
  
  
  1. function trampoline(f) { 
    2. 
  
  
  
  2.   while (f && f instanceof Function) { 
    3. 
  
  
  
  3.     f = f(); 
    4. 
  
  
  
  4.   } 
    5. 
  
  
  
  5.   return f; 
    6. 
  
  
  
  6. } 
    7.

你可以把这个函数称之为蹦床函数, 这个函数的作用就是放回一个新的函数，我们将它们俩结合起来的话，栈溢出的问题似乎就可以解决了

 
 
 
    
  
  
  
  1. // 可以试一试噢 
    2. 
  
  
  
  2. trampoline(fibonacci (10000)) 
    3.

这里的蹦床函数，我是参考别人的写法，似乎这样子写的话，不太行，我个人觉得这样子可以避免调用栈溢出，实际情况下，这样子是行不通的，哪里有行不通的，还望指出。

当然了，手动优化，可以将递归的过程改写成迭代的过程，就拿斐波那契数列这题来说，我们可以使用动态规划来完成，O（n）完成答案的更新。

 
 
 
    
  
  
  
  1. // 伪代码 
    2. 
  
  
  
  2. F[i] = F[i-1] + F[i-2] 
    3.

嗯，将一个尾递归函数转换成循环迭代函数，算是手动优化一种方式，在我们语言没有原生支持尾递归优化，那么可以考虑这种情况。

对于尾递归而言，我们需要了解优化它的原理，如果有必要的话，将递归的形式写成迭代的形式，通过迭代方式，降低重复值的计算，当然了，这个过程，有时候是比较难的，值得我们去思考。

分享文章：如何优化尾调用
转载注明：http://www.shufengxianlan.com/qtweb/news42/101092.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

建站公司知识

同城分类信息

成都企业网站建设　　 　西部信息服务器托管　　 　成都钢筋机械设备　　 　成都保温材料　　 　成都网站制作　　 　域名申请　　 　成都模板网站　　 　云服务器　　 　成都申请ssl证书　　 　四川服务器托管　　 　雪茄烟品牌　　 　眉山托管服务器　　 　腾讯免备案主机　　 　西部信息机房　　 　网站SEO优化排名　　 　定制级高端网站建设　　 　腾讯香港免备案空间　　 　友益建筑机械凿　　 　seo优化排名　　 　成都网站建设流程