专栏首页前端有的玩如何优化尾调用

如何优化尾调用

前言

经常看到关于尾递归这三个词,递归很多时候,都离不开我们,废话不多说,这次我们梳理一遍关于递归那些事。

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

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

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

尾调用

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

举个例子?

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

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

const fn = function () {
    const flag = f1()
    if(flag) {
        return flag
    } else {
        return f2()
    }
}

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


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

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

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

“按照阮一峰老师在es6的函数扩展中的解释就是:函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。如果在函数A的内部调用函数B,那么在A的调用帧上方,还会形成一个B的调用帧。等到B运行结束,将结果返回到AB的调用帧才会消失。如果函数B内部还调用函数C,那就还有一个C的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。

“这里的“调用帧”和“调用栈”,说的应该就是“执行环境”和“调用栈”。因为尾调用时函数的最后一部操作,所以不再需要保留外层的调用帧,而是直接取代外层的调用帧,所以可以起到一个优化的作用。

从上述的描述中,我们视乎可以理解成

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

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

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

手动优化

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

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

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

那么如何使用呢?

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

function fibonacci(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

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

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

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

// fibonacci(10000)
Uncaught RangeError: Maximum call stack size exceeded

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

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

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

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

// 可以试一试噢
trampoline(fibonacci (10000))

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

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

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

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

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

参考

  • 尾调用和尾递归

本文分享自微信公众号 - 前端有的玩(gh_918bae0a9616),作者:TianTianUp

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 尾调用优化

    尾调用(Tail Call)是函数式编程的一个重要概念,本文介绍它的含义和用法。 ? 一、什么是尾调用? 尾调用的概念非常简单,一句话就能说清楚,就是指某个函数...

    ruanyf
  • 尾调用优化

    [参考链接]((https://www.ruanyifeng.com/blog/2015/04/tail-call.html)

    flytam
  • 图解尾调用优化

    函数在调用的时候会在调用栈中 push 一个调用帧,每次执行完函数都会逐一弹出调用帧知道所有函数执行完毕,调用栈被清空:

    JS菌
  • 递归尾调用优化

    尾调用(Tail Call)是函数式编程的一个重要概念,就是指某个函数的最后一步是return调用另一个函数。

    wade
  • [译] ES6中的尾调用优化

    原文:http://exploringjs.com/es6/ch_tail-calls.html

    江米小枣
  • 如何优化长尾关键词

    对于很多小站长或者刚入职的推广人员来说,负责行业的核心关键词应该早就被其他竞争对手给抢先占有排名了,短期内应该是无法通过正常的seo优化来抢夺流量,因此长尾关键...

    竹清
  • JS 调用栈机制与 ES6 尾调用优化介绍

    调用栈的英文名叫做Call Stack,大家或多或少是有听过的,但是对于js调用栈的工作方式以及如何在工作中利用这一特性,大部分人可能没有进行过更深入的研究,这...

    OBKoro1
  • js 调用栈机制与ES6尾调用优化介绍

    本文中提到的链接,因为微信的限制,没有显示出来,查看文中链接,需要点击最下方的阅读原文链接

    OBKoro1
  • 面试官:说一说递归如何优化-尾递归优化

    编者荐语:本文旨在帮助大家掌握递归的性能优化方案——尾递归优化,以及如何对下列函数用尾递归进行优化?

    coder_koala
  • 如何符号化Objective-C调用栈如何符号化Objective-C调用栈

    本文讲述的是符号化“残破”的栈,如果你有一个系统生成的crash日志,请交给Xcode自带的symbolicatecrash脚本。

    且行且珍惜_iOS
  • 如何调优Spark Steraming

    云计算和大数据密不可分,这里有必要详细讨论下我的老本行——大数据领域。未来几年,我们将很荣幸地见证大数据技术的容器化。首先我们用几篇文章深入地了解一下大数据领域...

    云原生
  • ListView优化和列表首尾使用

    前面连续几期都在学习ListView的各种使用方法,如果细心的同学可能会发现其运行效率是有待提高的,那么本期就来一起学习有哪些方法技巧来优化ListVi...

    分享达人秀
  • 如何优化前端页面 / 如何优化网页

    HTML5学堂:如何优化前端页面 / 如何优化网页。作为前端开发人员来说,不但要开发出能兼容各大主流浏览器的页面,而且还需要懂得去优化前端页面。本文主要给大家讲...

    HTML5学堂
  • [译]Gas 优化 - 如何优化存储

    在Solidity[3](用于以太坊智能合约的编程语言)中,你拥有“内存(memory)”(想像计算机上的RAM)和“存储(storage)”(想像硬盘驱动器)...

    Tiny熊
  • 如何优化coding

    如何优化coding 前言 最近一直在做修改bug工作,修改bug花费时间最多的不是如何解决问题而是怎样快速读懂代码。如果代码写的好的,不用debug就可以一眼...

    Ryan-Miao
  • 如何做网站优化(SEO优化)

    信息化进入到如今,网站已经成为企业所不可或缺的必要配置,更注重企业信息化建设的企业,早已经成立信息部门。不仅仅如此,世界最大的网民国家——中国, 孕育最大的资源...

    数据通20847430
  • 如何用python“优雅”的调用有道翻译?

    其实在以前就盯上有道翻译了的,但是由于时间问题一直没有研究(我的骚操作还在后面,记得关注),本文主要讲解如何用python调用有道翻译,讲解这个爬虫与有道翻译的...

    bigsai
  • 设计师 | 如何在PPT结尾优雅的装13

    不论是做专业分享还是做工作汇报的时候,在PPT的结尾总需要一个强有力的收尾。这个收尾要同时具有以下四个特征:

    Shawn.W
  • group by如何优化?

    今天分享的内容是MySQL里面的group by语句,部分案例节选自极客时间的《MySQL45讲》,大家有兴趣可以购买相应课程进行学习,废话就不多说了,直接从例...

    AsiaYe

扫码关注云+社区

领取腾讯云代金券