如果你已经有一段时间的 JavaScript 开发经验,你很有可能会遇到递回这个定义,给定一个数字来阶乘,
就是一个标准的递回例子。
- n! = n * (n - 1) * ... * 1
- function factorial(n) {
- if (n === 0) {
- return 1;
- }
- return n * factorial(n - 1);
- }
上面所示的例子是阶乘函数最简单的实现。
为了更加完整的理解,我们来看看当
时是如何运行的:
- n = 6
现在,我们必须非常小心的去了解发生了什么事,所以我们可以明白接下来会发生什么。
当我们调用一个函数时,会发生许多事。调用函数后必须保存返回的位置,以及当前的信息(即
的值)。然后为新函数分配内存空间,并产生一个新的 frame(栈帧) 。
- n
这是继续下去,我们继续堆叠这些 frame(栈帧),然后我们释放堆栈,用它们返回的值替换函数调用。
要注意的另一件事是,我们的 function 处理过程中产生的的形状。如果我将此形状叫做递归,您可能不会感到惊讶。因此,我们有一个递归过程。
我们来看看这个函数的第二个实现
- function factorial(n, res) {
- if (n === 0) {
- return res;
- }
- return factorial(n - 1, res * n);
- }
我们可以通过定义一个内部函数来进一步封装功能。
- function factorial(n) {
- function inner_factorial(n, res) {
- if (n === 0) {
- return res;
- }
- return inner_factorial(n - 1, res * n);
- }
- return inner_factorial(n, 1);
- }
让我们看一下它是如何执行的:
您可能会注意到,展开堆栈后,我们不需要执行任何计算。我们只是返回一个值。但是,按照我们的规则,我们不得不将 state 储存为 frame(栈帧),即使它在这个中 chain 最后没有被任何的使用。
然而,我们的规则并不适用于所有语言。实际上,在 Scheme 中,这样的 chain 必须通过尾调用优化。这确保我们的 stack 不会被不必要的 frame(栈帧)填充。因此,我们先前的计算会看到这种方式︰
实上,看起来实在很像:
- res = 1;
- n = 6;
- while (n > 1) {
- res = res * n;
- n--;
- }
意思是,我们确实有一个反覆运算的处理,即使我们使用递归。这是多么酷啊?
好消息是 ES6 的 feature。只要你在尾递归调用,而且你的函数是 strict(严格) 模式,尾调用优化将储存并且踢除
错误。
- maximum stack size exceeded
来源: http://www.css88.com/archives/8015