尾调用优化

该文章由 leevare 发布于 ,归类于 Javascript

参考地址:http://es6.ruanyifeng.com/#docs/function

尾调用,就是说在函数的最后一步是调用另一个函数,例如

function a(value) {
    return b(value)
}

上述,在函数a的最后一步调用了函数b,这种调用方式就是尾调用。

那么,尾调用优化是什么意思呢?

我们知道,函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。如果在函数A的内部调用函数B,那么在A的调用帧上方,还会形成一个B的调用帧。等到B运行结束,将结果返回到AB的调用帧才会消失。如果函数B内部还调用函数C,那就还有一个C的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。

尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用帧,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用帧,取代外层函数的调用帧就可以了。

当在函数的尾部调用自身时,就成为尾递归。

普通的递归函数吗,由于要保存非常多个调用帧,所以就很容易发生堆栈溢出的错误。但是对于尾递归,就不存在这种错误,因为其只存在一个调用帧。

例如阶乘函数

function factorial(n) {
    if (n === 1) return 1
    return n * factorial(n - 1)
}

计算n的阶乘,所以就要保存n个调用记录

但是,如果使用尾递归的调用方式

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

这样在函数整个执行过程中,只保留一个调用记录。

当然,这看起来并不是通俗易懂,计算一个阶乘,还需要另外再传入第二个参数1,可以使用如下的改进方式

function tailFactorial(n, total) {
    if (n === 1) return total;
    return factorial(n - 1, n * total);
}

function factorial(n) {
    return tailFactorial(n, 1)
}

factorial(5)

也可以使用柯里化的方式,意思是将多参数的函数转换为单参数的形式。

function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

或者使用es6默认值的方式

function factorial(n, total = 1) {
    if (n === 1) return total;
    return factorial(n - 1, n * total);
}

factorial(5)

如果觉得我的文章对您有用,请您随意打赏。您的支持将鼓励我更加努力创作!

相关文章:

说点什么

avatar
300
  Subscribe  
提醒