浅谈尾递归_其他函数递归会释放内存吗

概念

尾调用（Tail Call）是函数式编程的一个重要概念，简单概括就是：某个函数的最后一步是调用另一个函数。

function f(x){
  return g(x);  // 函数f的最后一步是调用函数g，这就属于尾调用
}
// 尾调用不一定出现在函数尾部，只需要是最后一步即可
function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}
1
2
3
4
5
6
7
8
9
10

以下是几种不属于尾调用的函数

function f(x){
  let y = g(x);
  return y;  // 调用函数g以后，还有赋值操作
}

function f(x){
  return g(x) + 1; // 调用函数g以后，还有其他的操作
}
1
2
3
4
5
6
7
8

要想了解尾调用，必须先要了解函数的调用栈

函数调用栈

函数调会在内存中形成一个“调用记录”（“调用帧”），保存调用位置和内部变量等信息。如果在函数a中调用函数b，则会在a函数的调用记录上面，形成一个b函数的调用记录。等到b函数运行结束，将结果返回a函数，b函数的调用记录才会消失。如果b函数中还调用了函数c，那就会形成一个函数c的调用栈。以此类推，所有的调用记录，形成了一个“调用记录”。

函数执行在内存中的表现

function a (){
	return b()
}
1
2
3

es6优化之前

1. 执行到a函数体，第一个栈帧被推到栈上
2. 执行a函数体，到return语句，计算返回值需要先运行函数b
3. 执行到函数b，第二个栈帧被推到栈上
4. 执行函数b，计算其返回结果
5. 将函数b执行结果返回给函数a，然后函数a返回结果
6. 将所有栈帧弹出

es6优化之后

1. 执行到a函数体，第一个栈帧被推到栈上
2. 执行a函数体，到return语句，计算返回值需要先运行函数b
3. 引擎发现将第一个栈帧弹出也不影响后续操作，因为函数a的返回结果也是函数b的返回结果
4. 弹出函数a
5. 执行函数b，将函数b栈帧推到栈上
6. 计算函数b并返回计算结果
7. 将函数b栈帧弹出

很明显，尾调用优化之前，没嵌套一个内部函数，调用栈中便多了一个栈帧。尾调用优化之后，调用栈中至始至终都只有一个栈帧

尾调用的条件

• 代码在严格模式下执行
• 外部函数的返回值是对尾调用函数的调用
• 尾调用函数返回后不需要再执行额外的操作
• 尾调用不访问当前栈帧的变量（也就是说函数不是一个闭包）

尾递归

函数调用自身，称为递归。如果尾调用自身，则称为尾递归。
递归通常非常消耗内存，因为要同时保存成百上千个调用记录，很容易发生“栈溢出”错误，但是对于尾递归来说，由于只存在一个调用记录，所以不会发生“栈溢出”的错误。

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

factorial(5) // 120
1
2
3
4
5
6

上面是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录
如果改写成尾递归

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

factorial(5, 1) // 120
1
2
3
4
5
6

使用尾递归以后，函数始终只由一个调用记录，不会造成“栈溢出”，相对节省内存。
尾递归的实现，往往需要改写递归函数，确保在最后一步调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。比如上面的例子，阶乘函数 factorial 需要用到一个中间变量 total ，那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观，第一眼很难看出来。
可以采用es6中的默认参数来优化这个问题

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

factorial(5) // 120
1
2
3
4
5
6

上面的代码中，默认参数有值，所以调用的时候不再提供这个值。

严格模式

es6中的尾调用优化只有在严格模式才能生效，正常模式是无效的
因为在正常模式下，函数内部有2个参数可以跟踪函数的调用栈

• arguments：返回调用函数时的参数
• func.caller：返回调用当前函数的那个函数
  尾调用优化发生时，函数的调用栈会改写，因此上面两个参数会失去作用。严格模式禁用了这两个参数，所有尾调用仅在严格模式下生效