专栏首页coding个人笔记递归尾调用优化

递归尾调用优化

之前分享过递归,其中有一个优化就是尾调用。

先明确尾调用的概念:

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

function fn() { 
  return gn()
}

下面几种不是尾调用:

function fn() { 
  return gn() + 10//调用之后又赋值
}
function fn() { 
  gn()//没有return,或者说是return了undefined
}
function fn() { 
  var gnn = gn(); 
  return gnn//调用后还有操作
}

注意,是最后一步操作,不是放在最末尾,下面也算尾调用:

function fn(a) { 
  if(a > 10){ 
   return gn(10) 
  }else{ 
    return gn(20) 
  } 
  return gn()
}

之前分享过调用栈,如果不是尾调用,那么会生成一个调用栈,直到栈顶的执行完毕,才会释放之前形成的调用栈的内存。尾调用因为是最后一步操作,所以不需要保留之前的栈,也就不需要保存之前的内存,就是递归里面计算阶乘那两个函数。

注意,并不是所有的函数都能尾调用优化,要看你这个函数需不需要使用某些上个函数的变量或者什么的。

尾调用优化其实很大一部分就是递归函数在使用,因为递归函数调用的时候非常耗费内存,可能需要保存成百上千调用栈,很容易内存溢出。如果是尾递归就只有一个调用栈,能把复杂度O(n)的变成O(1)。

至于怎么改写递归变成可以使用尾调用就比较复杂了,需要根据不同函数去修改。比如阮一峰大神的例子:

function sum(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1);
  } else {
    return x;
  }
}
sum(1, 100000)

改成:

function sum(x, y) {
  if (y > 0) {
    return sum.bind(null, x + 1, y - 1);
  } else {
    return x;
  }
}

然后使用蹦床函数:

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

执行:

trampoline(sum(1, 100000))

你会发现,很多递归函数都能改成类似的,然后使用蹦床函数实现尾调用优化。

而ES6对尾调用有什么优化?就是函数默认值,在一些场景下,比如阶乘的递归,采用默认值实现尾递归优化。

(完)

本文分享自微信公众号 - coding个人笔记(gh_2ce38b49dae1),作者:wade

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

原始发表时间:2019-04-15

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 推荐几个数组的用法

    数组的使用方法,大都是普通的循环for、for in、forEach等,今天推荐三个新的方法,在一些特殊场景可以有很大作用。虽然这三个新方法fo...

    wade
  • toString()和valueOf()函数调用和优先级

    简单了说就是链式调用,链式调用的方法有很多,jQuery的,underscore的和lodash这三个库采用了不同的方式。而上面这个就简单多了:

    wade
  • 作用域、执行环境、作用域链

    作用域,之前有介绍过,JavaScript无块级作用域,只有函数作用域,简单点说就是JavaScript的作用域就是函数作用域。因为有函数作用域,所以我们有全局...

    wade
  • yield在WCF中的错误使用——99%的开发人员都有可能犯的错误[下篇]

    昨天写了《yield在WCF中的错误使用——99%的开发人员都有可能犯的错误[上篇]》,引起了一些讨论。关于yield关键字这个语法糖背后的原理(C#编译器将它...

    蒋金楠
  • Extjs-lesson3

    Ext.js 系列课程笔记「组件」更多精彩文章请关注公众号『Pythonnote』或者『全栈技术精选』

    小闫同学啊
  • Javascript \x 反斜杠x 16进制 编解码

    decode('\x5f\x63\x68\x61\x6e\x67\x65\x49\x74\x65\x6d\x43\x72\x6f\x73\x73\x4c\x61...

    用户1177380
  • 能用强化学习买卖比特币赚钱吗?能能能,当然能!

    AI 科技评论按:人工智能热潮还没过去,电子货币和区块链的热潮又滚滚而来。以 BTC(比特币)为代表的电子货币近半年来吸引了全世界的注意力,每个人都想在这个热潮...

    AI科技评论
  • R语言之GEO基因表达数据的下载整合

    source("https://bioconductor.org/biocLite.R")

    一粒沙
  • android MVVM开发模式(五)

    android MVVM开发模式(五) 上一讲我们说了@InverseBindingAdapter标记的事情。通过这个,我们可以实现view向数据方向的传递。从...

    用户1263308
  • 快速学习-EVM指令集

    cwl_java

扫码关注云+社区

领取腾讯云代金券