《javascript高级程序设计》学习笔记 | 10.12-10.13.递归
发布于 2 个月前 作者 simon9124 827 次浏览 来自 分享

关注前端小讴,阅读更多原创技术文章

相关代码→

10.12 递归

  • 递归函数是一个函数通过名称调用自己
function factorial(num) {
  if (num <= 1) {
    return 1
  } else {
    return num * factorial(num - 1)
  }
}
  • 函数逻辑与函数名是藕和的,因此将递归函数赋值给其他变量,并解除原函数名与函数之间的关系后,会报错
let anotherFactorial = factorial // 访问指针
factorial = null // 切断factorial与函数之间的联系
console.log(anotherFactorial(4)) // TypeError: factorial is not a function
  • 使用arguments.callee解藕(arguments.callee指向arguments所在函数的指针)
function factorial2(num) {
  if (num <= 1) {
    return 1
  } else {
    return num * arguments.callee(num - 1)
  }
}
let anotherFactorial2 = factorial2 // 访问指针
factorial2 = null // 切断factorial与函数之间的联系
console.log(anotherFactorial2(4)) // 24,arguments.callee指向anotherFactorial2
  • 严格模式下不能访问argumengts.callee(会报错),使用命名函数表达式达到目的
let factorial3 = function f(num) {
  if (num <= 1) {
    return 1
  } else {
    return num * f(num - 1) // 无论赋值给哪个变量,表达式f都不会变
  }
}
let anotherFactorial3 = factorial3
factorial3 = null
console.log(anotherFactorial3(4)) // 24

10.13 尾调用优化

  • ES6 新增非常适合尾调用内存管理优化机制,即外部函数的返回值是一个内部函数的返回值
function outerFunction() {
  return innerFunction() // 尾调用
}
  • ES6 优化之前,该例会在内存中如下操作(每多调用一次嵌套函数,就多增加 1 个栈帧):
    • 执行到outerFunction函数体,第 1 个栈帧被推到栈上
    • 执行outerFunction函数体到return语句,计算返回值要先计算innerFunction
    • 执行到innerFunction函数体,第 2 个栈帧被推到栈上
    • 执行innerFunction函数体,计算返回值
    • 将返回值传回outerFunction,然后outerFunction再返回值
    • 将栈帧弹出栈外
  • ES6 优化之后,该例会在内存中如下操作(无论调用多少次嵌套函数,都只有 1 个栈帧):
    • 执行到outerFunction函数体,第 1 个栈帧被推到栈上
    • 执行outerFunction函数体到return语句,计算返回值要先计算innerFunction
    • 因为innerFunction的返回值也是outerFunction的返回值,因此引擎发现可以把第一个栈帧弹出栈外
    • 弹出outerFunction的栈帧
    • 执行到innerFunction函数体,第 2 个栈帧被推到栈上
    • 执行innerFunction函数体,计算返回值
    • innerFunction的栈帧弹出栈外
  • ES6 尾调用优化的关键:如果函数的逻辑允许基于尾调用将其销毁,引擎就会那么多

10.13.1 尾调用优化的条件

  • 需确定外部栈帧真的没必要存在:
    • 外码需在严格模式下执行
      • 非严格模式允许使用的f.argumentsf.caller都会引用外部函数的栈帧
    • 外部函数的返回值是对尾调用函数的调用
    • 尾调用函数返回后,不需要执行额外的逻辑
    • 尾调用函数不是引用外部函数作用域中自由变量的闭包
;('use strict')

function outerFunction() {
  innerFunction() // 无优化,尾调用没有返回
}

function outerFunction() {
  let innerFunctionResult = innerFucntion()
  return innerFunctionResult() // 无优化,尾调用没有直接返回
}

function outerFunction() {
  return innerFunction().toString() // 无优化,尾调用返回后必须转型为字符串(有额外逻辑)
}

function outerFunction() {
  let foo = 'bar'
  function innerFunction() {
    return foo
  }
  return innerFunction() // 无优化,尾调用是一个闭包
}

function outerFunction(a, b) {
  innerFunction(a + b) // 有优化,栈帧销毁前执行参数计算
}

function outerFunction(a, b) {
  if (a < b) return a
  innerFunction(a + b) // 有优化,初始返回值不涉及栈帧
}

function outerFunction(condition) {
  return condition ? innerFunctionA() : innerFunctionB() // 有优化,2个内部函数都在尾部
}

10.13.1 尾调用优化的代码

  • 尾调用优化在递归场景下的效果最明显,因为递归代码最容易在栈内存中迅速产生大量栈帧
  • 斐波那契数列为例,使用尾调用优化减小浏览器的负担:
function fib(n) {
  if (n < 2) {
    return n
  }
  return fib(n - 1) + fib(n - 2) // 返回语句有相加操作,不符合优化条件
}

// 使用2个嵌套的函数重构斐波那契数列
;('use strict')

function fib(n) {
  return fibImp1(0, 1, n) // 以0为初始值,1作为第1个数字,n为第几个数字
}
function fibImp1(a, b, n) {
  if (n === 0) return a
  return fibImp1(b, a + b, n - 1) // 外部函数的返回值是内部函数的返回值,符合优化条件
}

总结 & 问点

  • 什么是递归函数?写一段代码表示阶乘,要求解耦函数逻辑和函数名
  • 严格模式下,写一段代码表示阶乘,要求函数名可以赋给任意变量
  • 什么是尾调用优化?其是如何优化内存管理的?尾调用优化的条件是什么?
  • 写一段代码,使用尾递归优化计算斐波那契数列
2 回复

我是不是眼神模糊了 我记得 v8 一直没有尾递归优化, 纵使es6你折腾来折腾去, 实际就是没有

@netwjx 的确是,v8做好了但默认不开启

回到顶部