factorial - 阶乘是如何计算的？

Question

说有一个函数来计算阶乘（n）

factorial(7) 是否为从 1 到 7 的 n 中的每一个创建 7 个函数对象

并在必要时使用这些值（对于阶乘（8），如阶乘（7）* 8）

Answer 1

这取决于语言和语言实现。

在许多函数式语言（例如 Haskell）中，函数保证不会改变任何内容。只返回一个值。这种副作用的缺乏允许语言记住/缓存或“记忆”函数调用的结果。

在不太复杂的语言中，7 个不同的函数调用帧可能会被放置在堆栈上并弹出。

许多函数式语言中正确编写的阶乘函数也将是尾递归的；在这种情况下，语言可能会选择简单地从函数底部跳到顶部，以避免创建另一个函数调用。在这种情况下，该语言将递归函数“免费”转换为循环。

Answer 2

这取决于，听起来你在谈论递归阶乘函数：

int factorial(int n) {
    return n>=1 ? n * factorial(n-1) : 1;
}

该函数将递归调用自身计算给定阶乘（n）所需的次数。

大多数情况下，所有递归函数都可以通过使用堆栈来累积连续结果来转换为迭代解决方案......

int factorial(int n) {
    int accu = 1;
    int i;
    for(i = 1; i <= n; i++) {
        accu *= i;
    }
    return accu;
}

Answer 3

它可以。你所问的听起来像是记忆——你存储以前的结果以加快计算速度。因此，例如，如果您计算 9!，则可以存储 1! 的值！.. 9!，如果你被要求 8! 稍后您可以返回存储的值。同样，如果要求 10!，您可以计算 10×9! 迅速地。

问题是阶乘（n）增长如此之快，对于较大的n值，您最终可能会使用大量存储空间，因此时空交易可能不值得。

另一个可以有效使用记忆的功能是计算斐波那契数。