栈与尾递归优化

发表于 更新于 分类于

JavaScript的ES2015标准已经被普及了很久了，众多的前后端应用也已经争先恐后地支持了这一标准，其中有一条也是最后一条很有意思，叫做尾递归优化

栈

不得不先说一下栈

栈是一个比较基础的数据结构，大家也广为熟悉。不过可能使用起来不会被感觉到。

栈可以被比喻为学生时代的判卷，做得快的同学（或者交白卷的同学）的卷子往往会最先放在讲台上，然后后面交卷的同学卷子会盖在之前同学的卷子上，最后做的慢的同学（或者仍然是交白卷的同学）的卷子会在最上面，这种有序堆叠卷子的行为被称为入栈

大家交完卷子的时候，老师会把卷子都抱走然后挨个判卷，最后交的卷子会被最先判到，按照顺序一张一张判完，这种行为叫做出栈

当然也有老师边交卷边判卷的，这也是被栈允许的，并不是一定要全部入栈后才能出栈，但是仍然在老师拿卷子的那个时间点，拿到的是最后交的卷子。

这种顺序被我们称为先入后出或者后入先出……what ever……

Javascript中实际上也是存在着很多栈的调用的，比如常见的数组操作，借用MDN的例子：

1
2
3
4
5
var animals = ['pigs', 'goats', 'sheep'];

animals.push('cows')
console.log(animals);
// 输出 ["pigs", "goats", "sheep", "cows"]

我们可以看到利用数组的push方法，我们将cows加入到了数组的末尾，这就是入栈

1
2
3
4
5
6
var animals = ['pigs', 'goats', 'sheep'];

console.log(animals());
// 输出 "sheep"
console.log(animals);
// 输出 ["pigs', 'goats"]

pop方法则为我们弹出了数组最后一个元素sheep，这就是出栈

调用栈

为什么要介绍栈

我们在编写代码的时候，做最多的事情很可能就是调用一个又一个的函数、方法来打成我们的目的，这里实际上就是在不停地使用栈的概念：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let end = () => {
  console.log('end');
}

let output = name => {
  console.log(name);
};

let start = name => {
  console.log('my name is');
  output(name);
  end();
};
start('huangStomach');

上述代码中，我们先调用了start函数，并在内部调用了output函数和end函数。当我们在调用start函数的时候，系统会为我们分配一块内存，存放我们调用的函数和它的参数：

1
2
3
[
  ['start', { name: 'huangStomach' }]
]

当然这么写只是打个比方，它会被计算机放入到内存块中。然后，我们调用了output函数，同样，计算机也会分配一块内存：

1
2
3
4
[
  ['output', { name: 'huangStomach' }],
  ['start', { name: 'huangStomach' }]
]

它会被放在第一个内存块上面，形成一个栈。这时候我们打印了name，这个函数也被执行完成并弹出栈。接下来我们会执行第二个函数end：

1
2
3
4
[
  ['end'],
  ['start', { name: 'huangStomach' }]
]

它会打印end并完成自己的使命然后被弹出，这时候栈内只剩下一个元素：

1
2
3
[
  ['start', { name: 'huangStomach' }]
]

然后我们的start方法也彻底的完成了使命，栈也被清空了。

递归调用栈

这和尾递归优化又有什么关系呢

比如我们可能有这样一个函数：

1
2
3
4
5
let factorial = (n, acc = 1) {
    "use strict";
    if (n <= 1) return acc;
    return factorial(n - 1, n * acc);
}

这个函数是用来求阶乘的，我们可以看到在函数的末尾我们又调用了自身，这被称为一个递归调用函数。

有时候我们不会使用遍历而是使用递归，可能是习惯问题可能是为了代码更加优美，但实际上两种方法都能为我们解决同样的问题。

当我们使用递归的时候，可以看到我们在函数内部不停的调用函数，这就会形成栈，当我们传入的参数是10可能还可以非常快的计算出来，但是如果我们传入100000，则会报错Maximum call stack size exceeded也就是stackoverflow。

当你冥思苦想，不断地为BUG唏嘘不已的时候，路过的扫地大妈会拍拍你的肩膀，告诉你：栈溢出了

为什么会这样呢？因为函数调用栈的原因，过多的递归调用则会使栈不停地堆叠，直到超出系统的安全限制，我们不得不修改我们的代码，或者干脆切换到遍历。

但是在ES2015中，我们拥有了尾递归优化，当我们处于ES2015环境并开启了严格模式后，尾递归优化就启动了。

当递归函数的末尾仅有对自身函数的调用的时候，系统则会进行检测，发现可以对之前的栈进行复用，我们不用再不停地进行入栈操作，递归也真正有了用武之地。