在Java函数式风格中递归计算阶乘

Question

我试图以函数式的方式计算阶乘。

我做了这个：

 private static Function<BigInteger, BigInteger> factorial = x -> BigInteger.ONE.equals(x)
        ? BigInteger.ONE
        : x.multiply(Main.factorial.apply(x.subtract(BigInteger.ONE)));

当我尝试获取11111!时，我遇到了StackOverflowError错误。

但是，如果我使用以下方法计算阶乘：

private static BigInteger factorial(BigInteger request) {
    if (BigInteger.ONE.equals(request)) return BigInteger.ONE;
    else return request.multiply(factorial(request.subtract(BigInteger.ONE)));
}

我可以在不出现StackOverflowError的情况下得到结果。

函数式编程风格是否更加低效？为什么？

- Vadim Chemodurov

---

我很困惑。这与“数组中所有元素的总和”有什么关系？ - Jörg W Mittag

这与函数式风格本身无关（顺便说一句：两种方法同样是函数式风格），主要区别——猜测一下——可能是Lambda可能会产生额外的开销，从而增加每次调用的堆栈大小，所以你会更快地耗尽堆栈空间。 - Mark Rotteveel

@JörgWMittag 对于误解我感到抱歉）我忘记更改问题的名称，起初我想从一本关于算法的书中取一个例子，但后来将其替换为阶乘计算。 - Vadim Chemodurov

也许它每次都会创建一个新的函数接口实例，并在栈上分配以进行优化... - dan1st

Java对尾递归没有优化，因此总会有限制。相关信息请参考：https://dev59.com/4VQJ5IYBdhLWcg3wqnwT - tevemadar

Answer 1

功能风格的电话呼叫次数是函数调用的两倍。请参见图像。

因此，尽管后者中堆栈大小增加到11,111个调用，但在函数式风格中增加了超过22,222个调用。我相信您的环境中堆栈限制应该在11111和22222之间，这就解释了为什么会出现错误。因此，在这种意义上，函数式风格似乎效率低下。

您可以使用下面链接中描述的-Xss来增加堆栈大小。

或者，最好使用尾递归，它看起来像这样：

private static BiFunction<BigInteger, BigInteger, BigInteger> factorialTR = (n, acc) -> BigInteger.ONE.equals(x)
    ? BigInteger.ONE
    : Main.factorialTR.apply(x.subtract(BigInteger.ONE), acc * n));

这将在Java中仍然导致StackoverflowError，因为它不支持尾递归优化。但是Scala、lisp支持，所以你不会遇到这个问题。

参考资料：

• 尾递归阶乘
• Leetcode解释(需要登录)
• 最大堆栈深度

- Anush Shrestha

---

我认为问题是在问为什么Lambda失败而函数不会，而不仅仅是为什么会发生StackOverflowError。 - 17slim

@17slim 谢谢。我已经更正了我的答案。 - Anush Shrestha

有趣的是，在我的测试中，两个版本都在13000-150000左右失败，每次测试的数字都不同。 - Jörg W Mittag

Answer 2

您的术语有点令人困惑。两个示例都是以函数式风格编写的：没有副作用，没有可变状态，没有循环。这两个示例都具有引用透明性。

此外，您似乎认为只有其中一个示例会抛出 StackOverflowError 。事实并非如此。这两个示例最终都会崩溃堆栈。

实际上，在我的测试中，这两个示例在相同的值处几乎都会崩溃堆栈。

对于lambda版本，我运行了多个测试，堆栈溢出发生的值每次略有不同，最小和最大值分别约为11000和15300左右。

对于方法版本，堆栈溢出通常在13901和13907之间发生。

最初，我认为lambda版本会比方法版本更早地溢出，因为它使用了更复杂的运行时机制（LambdaMetaFactory，方法句柄，调用站点，invokedynamic），这增加了堆栈大小。但是，看起来它不仅增加了堆栈大小，还增加了方差，因为它更依赖于运行时优化和启发式算法。

顺便提一下，你的代码（两个版本）存在相同的两个错误（实际上是同一个错误）：它不能处理零的阶乘（它是一），并且对于负数会进入无限递归。更正确的版本应该是这样的：

private static Function<BigInteger, BigInteger> factorial = 
    x ->
        x.compareTo(BigInteger.ZERO) < 0
        ? throw new ArgumentError()
        : BigInteger.ZERO.equals(x)
          ? BigInteger.ONE
          : x.multiply(App.factorial.apply(x.subtract(BigInteger.ONE)));

private static BigInteger factorial(BigInteger request) {
    if (request.compareTo(BigInteger.ZERO) < 0) throw new ArgumentError;
    if (BigInteger.ZERO.equals(request)) return BigInteger.ONE;
    else return request.multiply(factorial(request.subtract(BigInteger.ONE)));
}

- Jörg W Mittag