如果你已经有一段时间的 JavaScript 开发经验,你很有可能会遇到递回这个定义,给定一个数字来阶乘,n! = n * (n - 1) * ... * 1
就是一个标准的递回例子。
function factorial(n) { if (n === 0) { return 1; } return n * factorial(n - 1); }
上面所示的例子是阶乘函数最简单的实现。
为了更加完整的理解,我们来看看当 n = 6
时是如何运行的:
- factorial(6)
- 6 * factorial(5)
- 5 * factorial (4)
- 4 * factorial(3)
- 3 * factorial(2)
- 2 * factorial(1)
- 1 * factorial(0)
- 1
- (恢复先前的执行) 1 * 1 = 1
- (恢复…) 2 * 1 = 2
- (…) 3 * 2 = 6
- … 4 * 6 = 24
- 5 * 24 = 120
- 6 * 120 = 720
- factorial(6) = 720
现在,我们必须非常小心的去了解发生了什么事,所以我们可以明白接下来会发生什么。
当我们调用一个函数时,会发生许多事。调用函数后必须保存返回的位置,以及当前的信息(即 n
的值)。然后为新函数分配内存空间,并产生一个新的 frame(栈帧) 。
这是继续下去,我们继续堆叠这些 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); }
让我们看一下它是如何执行的:
- factorial(6)
- 使用 (n = 6, res = 1) 调用内部匿名函数 (iaf)
- iaf(5, 1 * 6)
- iaf(4, 6 * 5)
- iaf(3, 30 * 4)
- iaf(2, 120 * 3)
- iaf(1, 360 * 2)
- iaf(0, 720)
- 720
- 720
- 720
- 720
- 720
- 720
- 720
- iaf (6, 1) = 720
- factorial(6) = 720
您可能会注意到,展开堆栈后,我们不需要执行任何计算。我们只是返回一个值。但是,按照我们的规则,我们不得不将 state 储存为 frame(栈帧),即使它在这个中 chain 最后没有被任何的使用。
然而,我们的规则并不适用于所有语言。实际上,在 Scheme 中,这样的 chain 必须通过尾调用优化。这确保我们的 stack 不会被不必要的 frame(栈帧)填充。因此,我们先前的计算会看到这种方式︰
- factorial(6)
- iaf(6, 1)
- iaf(5, 6)
- iaf(4, 30)
- iaf(3, 120)
- iaf(2, 360)
- iaf(1, 720)
- iaf(0, 720)
- 720
实上,看起来实在很像:
res = 1; n = 6; while(n > 1) { res = res * n; n--; }
意思是,我们确实有一个反覆运算的处理,即使我们使用递归。这是多么酷啊?
好消息是 ES6 的 feature。只要你在尾递归调用,而且你的函数是 strict(严格) 模式,尾调用优化将储存并且踢除 maximum stack size exceeded
错误。
英文原文:
最新评论
写的挺好的
有没有兴趣翻译 impatient js? https://exploringjs.com/impatient-js/index.html
Flexbox playground is so great!
感谢总结。
awesome!
这个好像很早就看到类似的文章了
比其他的教程好太多了
柯理化讲的好模糊…没懂