内存的清道夫——函数的尾调用

函数的尾调用

尾调用是什么,它能解决什么问题,他的存在意味着什么,为什么我叫他内存的清道夫,下面我将带读者通过概念作用尾巴递归三个方面来学习使用函数的尾调用。

尾调用概念

尾调用指的是在函数的最后一步通过return调用另一个函数

function fn() {
    return _fn()
}

如上就是一个标准的函数尾调用

尾调用的作用

尾调用的作用非常重要,它可以为我们节省在函数调用时的内存,这也是我为什么叫它内存的清道夫,我们先来看一下函数执行的底层原来,再来了解尾调用是如何节省内存的

函数执行中的帧

伴随函数的执行,函数会在内存中生成一个调用帧,我们先设定A,B,C三个函数,通过下面的形式调用(注意下面是普通的函数调用)

fn_A() {
    fn_B()
}
fn_B() {
    fn_C()
}

如上:A函数执行,执行B函数,B函数内执行C函数,函数执行的过程是这样的:

  • A执行生成一个A调用帧,在内部执行B函数
  • B函数生成一个调用帧在A调用帧上方
  • B函数内执行C函数,C函数执行生成一个调用帧在B调用帧上方,其本质就是一个调用帧栈
  • C函数执行完毕,C调用帧出栈
  • B函数执行完毕,B调用帧出栈
  • A函数执行完毕,A调用帧出栈

通过以上过程就能了解函数执行中会生成调用帧占用内存,而不断地嵌套函数会占据越来越多的内存空间,下面我们来看看尾调用是如何改变这一过程达到优化的效果。

尾调用优化的过程

那么如果我们使用尾调用来执行函数内部的函数。它的过程是怎么样的?

fn_A() {
   return fn_B()
}
fn_B() {
   return fn_C()
}
  • A执行生成一个A调用帧入栈
  • 由于B函数在尾部执行,无需A的资源,所有A调用帧出栈,生成B调用帧入栈
  • B函数执行,尾部调用C函数,无需B的资源,B调用帧出栈出栈,生成C调用帧入栈
  • C执行结束,C调用帧出栈

尾调用:在执行A函数中的B函数的前就可以对A调用帧进行出栈处理,也就是说在这连续嵌套一过程中,栈中只有一个调用帧,大大节省了内存空间,成为一名合格的内存清道夫!

注意:真正的尾调用是需要考虑到资源的占用,即B函数执行不需要A函数内的资源,才能算是真正的尾调用

一种特殊的尾调用

当尾调用的函数是自身的时候就诞生了一种特殊的尾调用形式即尾递归

function fn() {
    return fn()
}

正常的递归使用如果过多的话会产生栈溢出的现象,所以可以使用尾递归来解决这个问题,我们来看下面的例子

function fn(n) {
    if(n === 1) return 1
    return n * fn(n-1)
}
console.log(fn(6)); // 720

如上是一个普通的递归函数求阶乘,那么我们可以使用尾递归来优化这个过程

function fn(n, tol) {
  if (n === 1) return tol;
  return fn(n - 1, n * tol);
}
console.log(fn(6, 1)); // 720

尾递归的实现

需要注意的是我们只有在严格模式下,才能开启尾调用模式,所以在其他场景我们需要使用其他的解决方案来替代尾调用,尾递归也同理,因为尾递归的过程其实是循环调用,所以利用循环调用可以变相实现尾递归,这里涉及到了一个名词:蹦床函数

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

如上就是一个蹦床函数的封装,传入的参数是要进行递归的函数,其作用是代替递归,进行循环调用传入参数,下面我们来看看具体应用

function num (x,y) {
    if(y > 0) {
        return num(x+1,y-1)
    }else {
        return x
    }
}
num(1,10000) // Maximum call stack size exceeded

Maximum call stack size exceeded就是栈溢出的报错,递归直接使用如果次数过多就会造成这样的现象,那么我们下面搭配蹦床函数使用。

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
​
function num(x, y) {
  if (y > 0) {
    return num.bind(null, x + 1, y - 1);
  } else {
    return x;
  }
}
console.log(trampoline(num(1, 1000))); // 1001

通过蹦床函数将递归函数纳入,以循环的形式调用,最后得到结果,不会发生栈溢出现象,总结来看,尾调用是切断函数与尾调用函数之间的联系,用完即释放,藕断丝不连,不占用内存的效果。